How to prove this equality, $log(O(5^{n})) = O(n)$?

Question

If there was no big O notation in logarithm, my idea would be to take exponent $n$ and to put it in front of the algorithm, so we would get this:

$n\log(5) = O(n)$ which, if my thinking is right, is correct. We have constant $log(5)$ multiplying $n$, so we just need to find some $c$, for which:

$c\ n \geq n\ log(5)$.

So my problem is how to get rid of O notation in logarithm? What would be valid proof or explenation for this?

The statement is true if you only consider increasing functions, but not in general. Is this one of the assumptions you're working under? What is your definition of $O(\cdots)$? — Antonio Vargas, Oct 22 '17 at 14:33

score 0 · Answer 1 · answered Oct 22 '17 at 11:41

The underlying meaning of the $O$-notation is a statement, namely that some quantity is bounded above by some suitable multiple of another quantity. So to get rid of the $O$ you just translate "$x=\log O (5^n)$" into the statement, "for some $M>0$, $x \leqslant \log M \cdot 5^n$." Then you can use the usual rules for logarithms.

How to prove this equality, $log(O(5^{n})) = O(n)$?

1 Answers1