2
$\begingroup$

Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$?

Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.

$\endgroup$
1
  • $\begingroup$ Note that Landau notation does not per se have anything to do with time complexity. "$O(f)$" is a mathematical construct that can be used to reason about algorithmic costs and complexities; but you're interested in domain-independent properties. $\endgroup$
    – Raphael
    Commented Nov 3, 2019 at 19:20

1 Answer 1

3
$\begingroup$

$O(\log(n))$ and $O(\log(n-1))$ contain the same set of functions.

The inclusion $O(\log(n-1)) \subseteq O(\log(n))$ is trivial. As for $O(\log(n-1)) \supseteq O(\log(n))$, let $f(n) \in O(\log(n))$ and let $c \ge 1$ and $n_0 \ge 3$ be such that: $$ f(n) \le c \log(n) \quad \forall n \ge n_0. $$

We have: $$ f(n) \le c \log(n) = c + c \log(n/2) \le c + c \log(n-1) \le 2c \log(n-1). $$

Showing that $f(n) \in O(\log(n-1))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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