Which constants can be ignored in Big O for time complexity - exponential cases?

Question

The obvious one is a constant on a linear term for example 2n, 4n and 8n are all just n or O(n).

But what about the exponential constant 1.6^n and 2^n. In this case the constant seems to have a greater effect on the time complexity.

Also there is not really a convenient way to write a catch all for exponential time complexity.

O(K^n) perhaps.

In this cheat sheet, they seem to use O(2^n) does that mean that all exponential complexities should be written that way?

Probably not.

Answer 1

You're right that 2n, 4n and 8n are all just O(n), and you're also right that O(1.6ⁿ) is not the same as O(2ⁿ). To understand why, we need to refer to the definition of big O notation.

The notation O(...) means a set of functions. A function f(n) is in the set O(g(n)) if and only if, for some constants c and n₀, we have f(n) ≤ c * g(n) whenever n ≥ n₀. Given this definition:

• The function f(n) = 8n is in the set O(n) because if we choose c = 8 and n₀ = 1, we have 8n ≤ 8 * n for all n ≥ 1.
• The function f(n) = 2ⁿ is not in the set O(1.6ⁿ), because whichever c and n₀ we choose, 2ⁿ > c * 1.6ⁿ for some sufficiently large n. We can choose n > log₂ c + n₀ log₂ 1.6 for a concrete counterexample.
• Note however that f(n) = 1.6ⁿ is in the set O(2ⁿ), because 1.6ⁿ ≤ 1 * 2ⁿ for all n ≥ 1.

For a "catch-all" way of writing exponential complexity, you can write 2^O(n). This includes exponential functions with arbitrary bases, e.g. the function f(n) = 16ⁿ since this equals 2⁴ⁿ, and 4n is in the set O(n). It's an abuse of notation, since raising the number 2 to the power of a set of functions doesn't really make sense in this context, but it is common enough to be understood.

Answer 2

That is correct. The cheat sheet you linked to here can not show all the different complexities so it picks the most common ones.

Simply put, if you have a function growing at 3 ^ n. It can not be classified as 2 ^ n because it will break the definition of Big O.

The some what complex looking math that describes Big O is simply saying that it can't ever be bigger. And also ignore linear growth constants.

f(n) ≤ c * g(n) whenever n ≥ n0