Nishiura_high
- 7
- 0
My textbook says O(3log2 n) can be written as O(nlog2 3). Why is that?
Thank you.
Thank you.
Big-Oh algebra with logarithms that I don't get?
- Thread starter Nishiura_high
- Start date
-
- Tags
- Algebra Logarithms
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
Discussion
- 16,335
- 258
Welcome to PF, Nishiura_high! 
One of the log rules is that ##\log a^b = b \log a##.
So:
$$\log_2(3^{\log_2 n}) = \log_2 n \cdot \log_2 3$$
and also:
$$\log_2(n^{\log_2 3}) = \log_2 3 \cdot \log_2 n$$
Nishiura_high said:
One of the log rules is that ##\log a^b = b \log a##.
So:
$$\log_2(3^{\log_2 n}) = \log_2 n \cdot \log_2 3$$
and also:
$$\log_2(n^{\log_2 3}) = \log_2 3 \cdot \log_2 n$$