Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Yves Daoust May 7 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 7 at 21:14
    
Then $f(n)=\mathcal{O}(g(n))$ cannot be written. And what set would $\mathcal{O}(f(n))$ deemed to be ? –  Yves Daoust May 7 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 mathworld.wolfram.com/Big-ONotation.html –  user2357112 May 7 at 22:23
    
@user2357112: Interesting. It confirms that either way the question is ill-formulated. –  Yves Daoust May 8 at 6:38

1 Answer 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.

share|improve this answer
    
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 7 at 21:00
    
@user3576199: If their bases are not the same, then $f(n) \ne g(n)$. –  user2357112 May 7 at 21:01
    
what if I have something like log(n) = klog(n)? k is a constant or something else. –  user3576199 May 7 at 21:04
    
and they have different base but log(n) equal to klog(n). –  user3576199 May 7 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 7 at 21:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.