0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Antonio Vargas Oct 22 '17 at 14:33
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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