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

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

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

## 1 Answer

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.