CODEWITHSUNDEEP
big-oasymptotic-complexity
Marcin Robaszyński
Marcin Robaszyński

Reputation: 782

Big O notation for exponential and logarithmic complexity

There are a lot of questions about big O notation, but I didn't found clear answer for this question.

We write that:
O(5n) = O(n)
and
O(3n^2 + n + 2) = O(n^2)

Can we write that:
O(2^(2n)) = O(2^n)?

The same for logarithmic complexity: O(n log(4n)) = O(n log(n))?

Upvotes: 1

Views: 8065

Answers (1)

John Kugelman
John Kugelman

Reputation: 361625

The only constants you can remove are additive and multiplicative ones. Meaning O(f(n)) = O(f(n) + C) = O(C × f(n)).

22n = (2n)2. This 2 constant cannot be ignored as it is an exponent. Just as O(n) and O(n2) are different complexity classes, so are O(2n) and O(22n).

On the other hand, yes, O(n log 4n) = O(n log n). We can use a logarithmic identity to turn the 4 into an multiplicative constant: O(n log 4n) = O(n (log n + log 4)) = O(n log n + (log 4) n) = O(n log n + n) = O(n log n).

Upvotes: 14

Related Questions