I am trying too prove:
log2(9n) is BigO(log2n)
I know this is achieved by Big-O forumla/proof f(n) <= C*g(n) where C is a constant. So far, I have:
log2(9n) <= 5*log2(n)
log2(9) + log2(n) <= 5*log2(n)
...To eliminate log, divide by log2(n)...
(log2(9) + log2(n)) / log2(n) <= 5*log2(n)/log2(n)
(log2(9) + log2(n)) / log2(n) <= 5
Now, I have forgotten the basic algebra to eliminate that log on the left side of the equation. From what I have found around the web, the solution is to reduce this to a single value log2(9) something and compare it to 5. So you would get something like (although I 99% sure this is incorrect):
log2(9) + log2(n) / log2(n) <= 5
3.17 + 1 <= 5 and therefore true.
How do I eliminate this extra log2(n)? Do I use log division property to create a subtraction? I have searched all over and have not found what I am looking for. Also, sorry about the formatting - did not know how to do the math type - go ahead and roast me.
Note that for all $n \ge 2$ we have $\frac{\log_2 9}{\log_2 n} \le \frac{\log_2 9}{\log_2 2} = \log_2 9 \le 3.17$.