-2

If $f(n)=g(n)$, can we just say that $\mathcal{O}(f(n))=\mathcal{O}(g(n))$? ($f$ and $g$ are two $\log$ functions)

Is it definitely yes? if not please describe why.

Thomas Russell
  • 10,425
  • 5
  • 38
  • 66
user3576199
  • 1
  • I am not sure that the equation $\mathcal{O}(f(n))=\mathcal{O}(g(n))$ makes any sense. When you write $f(n)=\mathcal{O}(g(n))$, you mean that $f$ is bounded by $g$, but that's a shorthand notation, not an equality. –  May 07 '14 at 21:06
  • @YvesDaoust: Treating $\mathcal{O}(f(n))$ as a set, we do have $\mathcal{O}(f(n))=\mathcal{O}(g(n))$ as an equality of sets, though. – user2357112 May 07 '14 at 21:14
  • Then $f(n)=\mathcal{O}(g(n))$ cannot be written. And what set would $\mathcal{O}(f(n))$ deemed to be ? –  May 07 '14 at 21:17
  • @YvesDaoust: People who don't like writing $f(n)=\mathcal{O}(g(n))$ often define $\mathcal{O}(g(n))$ as the set of functions $f$ for which there is some constant $k$ such that $f(x)<kg(x)$ for all integers $x$, and write $f(n) \in \mathcal{O}(g(n))$. I always use $\in$ instead of $=$ for Big O notation where typographical restrictions don't require $=$, but I don't know how common that is. A quick search shows the notation used at http://mathworld.wolfram.com/Big-ONotation.html – user2357112 May 07 '14 at 22:23
  • @user2357112: Interesting. It confirms that either way the question is ill-formulated. –  May 08 '14 at 06:38

1 Answers1

1

Of course we can. If $f(n)=g(n)$, then $f$ and $g$ are the exact same function, and it doesn't matter whether we use the name $f$ or $g$ to refer to it in any context we choose.

user2357112
  • 2,401
  • Got it. Thank you. And it doesn't matter whether their logarithmic bases are same, because the base can be omitted under big-O. Right? – user3576199 May 07 '14 at 21:00
  • @user3576199: If their bases are not the same, then $f(n) \ne g(n)$. – user2357112 May 07 '14 at 21:01
  • what if I have something like log(n) = klog(n)? k is a constant or something else. – user3576199 May 07 '14 at 21:04
  • and they have different base but log(n) equal to klog(n). – user3576199 May 07 '14 at 21:05
  • @user3576199: Then that's an entirely different question from what you asked, and it'd be good to be more careful about that in the future. We still have $\mathcal{O}(f(n)) = \mathcal{O}(g(n))$ from the definition of big-O notation, since it's trivial to find constants for which $af(n)<g(n)$ and $bg(n)<f(n)$. – user2357112 May 07 '14 at 21:06
  • $\log_A(n)=\mathcal{O}(\log_B(n))$ is indeed true for any two bases $A$ and $B$. $\mathcal{O}(\log_A(n))=\mathcal{O}(\log_B(n))$ has no meaning. –  May 07 '14 at 21:13