SME
Data Structures & Algorithms · Problem type
Ordering growth rates
Use this for “Order n², log n, 2ⁿ, n log n, √n, n!, 1 and n from slowest to fastest growth.”
Put in order
Put the running times in order, the slowest-growing first.
1
?
2
?
3
?
4
?
5
?
6
?
7
?
8
?
Assumptions
•
f grows slower than g when f(n) ÷ g(n) goes to 0 as n grows, whatever the constants.
•
Every log grows slower than every power nᵏ with k > 0, and every power slower than 2ⁿ.
•
The base of the log does not matter: log₂n and log₁₀n differ only by a constant factor.
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.