Is $\log_2(2n) \in O(\log_2(n))$ ?
I don't know how to prove whether this is true or false. Any help is appreciated
1
-
$\begingroup$ $\log_x (yn) \in O(\log(n))$ for all constant $x, y$ except for "degenerate" values [such as $x$ being 0, 1, or negative] or $y$ being nonpositive. $\endgroup$– ṂųỻịgǻňạcểơửṩFeb 5, 2020 at 14:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
We have: $$\log_2(2n) = \log_2(2) + \log_2(n) = 1 + \log_2(n) < 2 \times \log_2(n)$$
You can take $c = 2$ and as $\log_2(2n) < c \times \log_2(n)$ for $n > 2$, we can say $\log_2(2n) \in O(\log_2(n))$.
$\begingroup$
$\endgroup$
$\log_2(2n) \in O(\log_2(n))$ is true.
Asymptotic complexity helps us determine the rate at which an algorithm grows with respect to the input size. Therefore, constants are negligible.
Note that the base of the logarithm should also be ignored since it is a constant factor.
Then, the question reduces to: does $\log(n)$ grow at the same rate or slower than $\log(n)$? Of course it does.
You may want to have a look at this post. Justification for neglecting constant factors in Big O
