Common Growth Rates and Estimating from Constraints
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A problem gives you a limit on n, and the limit hides the answer to "which approach?". Learn the usual growth rates, then use the limit to decide before you write a line.
The growth rates you will meet
Growth rate is the family a step count belongs to as n grows: constant, logarithmic, linear, n log n, quadratic or exponential. It decides whether a solution scales.
Almost every solution falls in one family. From cheapest to dearest: O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ). Print the steps each one needs.
import math
for n in (10, 1000, 100000): print(n, round(math.log2(n)), n, round(n * math.log2(n)), n * n)Example 1 · A table for n = 1000
import math
n = 1000rows = { "O(1)": 1, "O(log n)": int(math.log2(n)), "O(n)": n, "O(n log n)": int(n * math.log2(n)), "O(n^2)": n ** 2,}for name, steps in rows.items(): print(f"{name:<11}{steps:>10,}")O(1) 1 O(log n) 9 O(n) 1,000 O(n log n) 9,965 O(n^2) 1,000,000
What this code does
- The dictionary maps each growth rate to its step count for n = 1000.
- The f-string pads the name to 11 characters and the count to 10, with commas.
- O(n²) is a hundred times the O(n log n) row.
Each row shows n, then log n, n, n log n and n². Going from n = 1000 to 100000 barely moves log n but multiplies n² by ten thousand.
Halving gives log n
Logarithmic time, written O(log n), means each step cuts the remaining work in half. A million items need about 20 steps. Binary search is the classic example.
If every step throws away half of the remaining work, the number of steps is the number of times you can halve n. For a million items that is only about 20.
def halving_steps(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
print(halving_steps(1000))print(halving_steps(1_000_000))Example 2 · Binary search takes about 20 steps
def binary_steps(items, target): low, high, steps = 0, len(items) - 1, 0 while low <= high: steps += 1 mid = (low + high) // 2 if items[mid] == target: return steps if items[mid] < target: low = mid + 1 else: high = mid - 1 return steps
ids = list(range(1_000_000))print(binary_steps(ids, 765_432))print(binary_steps(ids, -5))17 19
What this code does
- Each loop compares the middle item and throws away half of the range.
- A found id and a missing id both take about 20 steps. A front-to-back scan could need a million.
- The list must already be sorted.
One thousand items need 9 halvings and one million need 19. A thousand times more data added only ten steps.
Estimate from the constraints
Constraint is a limit the problem gives for its input, such as 1 ≤ n ≤ 100000. It tells you which growth rates are fast enough before you write any code.
Python runs roughly ten million simple steps per second. With a one to two second limit, aim for about 10⁷ steps in total. Put n into each growth rate and compare.
def fits(steps, budget=10_000_000): return steps <= budget
n = 100_000print("O(n)", fits(n))print("O(n log n)", fits(n * 17))print("O(n squared)", fits(n * n))Example 3 · Brute force vs a dictionary: two items that add to a target
def pair_brute(prices, target): checks = 0 for i in range(len(prices)): for j in range(i + 1, len(prices)): checks += 1 if prices[i] + prices[j] == target: return (i, j), checks return None, checks
def pair_dict(prices, target): seen, checks = {}, 0 for j, price in enumerate(prices): checks += 1 if target - price in seen: return (seen[target - price], j), checks seen[price] = j return None, checks
prices = list(range(1, 2001))print(pair_brute(prices, 9999))print(pair_dict(prices, 9999))(None, 1999000) (None, 2000)
What this code does
- No two prices add to 9999, so both methods must look at everything.
- The brute force checks every pair: O(n²), nearly two million checks.
- The dictionary asks "have I already seen the partner price?" once per item: O(n), 2000 checks.
Example 4 · The slowest approach that fits
def slowest_fit(n, budget=10_000_000): if n * n <= budget: return "O(n^2)" if n * n.bit_length() <= budget: return "O(n log n)" if n <= budget: return "O(n)" return "O(log n) or O(1)"
for n in (1000, 100_000, 5_000_000, 10**12): print(n, slowest_fit(n))1000 O(n^2) 100000 O(n log n) 5000000 O(n) 1000000000000 O(log n) or O(1)
What this code does
n.bit_length()is about log2 of n, son * n.bit_length()estimates n log n.- The function returns the slowest growth rate that still fits the budget.
- For n = 10¹² only a logarithmic or constant solution can run in time.
For n = 100000, O(n) and O(n log n) fit and O(n²) needs ten billion steps. The limits in a problem tell you which approach to look for.
Exponential growth is a wall
Exponential time, written O(2ⁿ), means the steps double with every extra item. n = 30 is already over a billion steps, so only tiny inputs can use it.
O(2ⁿ) doubles with every extra item. It is fine for n up to about 20 and hopeless beyond 30. Spot it in code that tries every subset or calls itself twice per step.
for n in (10, 20, 30, 40): print(n, 2 ** n)Example 5 · Why plain recursion explodes
from functools import lru_cache
slow_calls = 0fast_calls = 0
def fib_slow(n): global slow_calls slow_calls += 1 return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)def fib_fast(n): global fast_calls fast_calls += 1 return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)
print(fib_slow(25), slow_calls)print(fib_fast(25), fast_calls)75025 242785 75025 26
What this code does
fib_slowcalls itself twice and recomputes the same values again and again: about 1.6 to the power n calls.lru_cacheremembers each answer, so each n is computed once: 26 calls, O(n).- Same answer, 242785 calls against 26.
Example 6 · Counting subsets
from itertools import combinations
n = 10count = sum(1 for size in range(n + 1) for _ in combinations(range(n), size))print(count, 2 ** n)print(2 ** 30)1024 1024 1073741824
What this code does
- A set of n items has 2ⁿ subsets, because each item is either in or out.
- Listing them all for 10 items gives 1024. For 30 items it would give over a billion.
- This is why "try every subset" works only when n is about 20 or less.
Ten more items multiplied the work by about a thousand each time. At n = 40 it is over a trillion steps.
Next step
Check your understanding
11 quick questions