For the following pairs of functions, circle the function that is asymptotically larger.

Question

1. n^2 or (n+n)^2
2. 2^n or 4^n
3. n! or n^n
4. 2^(lg n) or n
5. n or n+n
6. lg(n!) or n(lg(n))
7. lg(2^n) or lg(4^n)
8. log10(n) or log2(n)
9. 2^n or 2^(n+1)
10. n! or (n+1)!
11. 2^n or 2^(n+n)
12. (n+1)^n or n^n

Answer 1

Before working through these, here is the thing that makes the whole list much easier: most of these pairs are the same order, so on most of them there is nothing to circle. Asymptotic growth ignores constant factors, so anything that merely multiplies a function by a fixed number does not make it asymptotically larger.

The reliable method for every single one is the same. Form the ratio g(n)/f(n) and ask what it does as n grows. If it runs off to infinity, g is larger. If it goes to 0, f is larger. If it settles on a constant, neither is larger and they are the same order. I will write lg for log base 2.

1. n² vs (n+n)²
(n+n)² = (2n)² = 4n². Ratio is 4. Same order, both Θ(n²).

2. 2ⁿ vs 4ⁿ
4ⁿ = (2²)ⁿ = 2²ⁿ, so the ratio is 2ⁿ, which goes to infinity. 4ⁿ is larger.

3. n! vs nⁿ
Both are products of n factors, but in n! the factors are n, n−1, ..., 1 while in nⁿ every factor is n. The ratio nⁿ/n! goes to infinity. nⁿ is larger.

4. 2^{lg n} vs n
Raising 2 to the log base 2 of n undoes the log, so 2^{lg n} = n exactly. Same, they are literally equal.

5. n vs n+n
n+n = 2n. Ratio is 2. Same order.

6. lg(n!) vs n lg n
Stirling gives lg(n!) = n lg n − n lg e + O(lg n), so the ratio goes to 1. Same order, both Θ(n log n). This one is worth remembering, since it is the reason comparison based sorting cannot beat Ω(n log n).

7. lg(2ⁿ) vs lg(4ⁿ)
These are n and 2n. Ratio is 2. Same order. Taking a log collapsed the gap from item 2 into a constant factor.

8. log₁₀(n) vs log₂(n)
Change of base: log₂ n = log₂(10) · log₁₀ n ≈ 3.32 · log₁₀ n. A fixed multiple. Same order. This is exactly why people write O(log n) without ever naming a base.

9. 2ⁿ vs 2ⁿ⁺¹
2ⁿ⁺¹ = 2 · 2ⁿ. Ratio is 2. Same order. Keep this one next to item 11.

10. n! vs (n+1)!
(n+1)! = (n+1) · n!, so the ratio is n+1, which goes to infinity. (n+1)! is larger. Compare with item 9: adding 1 to an exponent multiplies by a fixed 2, but adding 1 to a factorial multiplies by something that itself grows.

11. 2ⁿ vs 2ⁿ⁺ⁿ
2ⁿ⁺ⁿ = 2²ⁿ = 4ⁿ, so the ratio is 2ⁿ. 2ⁿ⁺ⁿ is larger. Doubling the exponent is a real change, unlike adding a constant to it.

12. (n+1)ⁿ vs nⁿ
The ratio is (n+1)ⁿ/nⁿ = (1 + 1/n)ⁿ, and that famous limit equals e ≈ 2.718. A constant. Same order. This is the trap on the list: it looks like item 10 but it behaves like item 9.

The pattern worth taking away. Multiplying by a constant, or adding a constant to an exponent, or switching log bases, never changes the order. Those are items 1, 4, 5, 7, 8, 9 and 12. What does change the order is scaling the exponent itself, or multiplying by a factor that grows with n. Those are items 2, 3, 10 and 11. If you can sort each problem into one of those two buckets, you rarely need to compute anything at all.