Growth rates and asymptotic notation
Count operations to see how logarithmic, linear, and quadratic work grow with input size.
On this page
Loops, functions, and integer division.
- Count operations to see how logarithmic, linear, and quadratic work grow with input size.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Analysis of algorithms studies how the resources an algorithm uses, usually time or memory, grow as the input size n grows. Instead of timing a program on one machine, we count the basic operations it performs. That count is a function of n, and we compare functions by how fast they grow.
Asymptotic notation compares growth while ignoring constant factors and lower-order terms. f(n) = O(g(n)) means there are constants c > 0 and n0 such that f(n) <= c·g(n) for every n >= n0, so g is an upper bound. Ω gives a lower bound in the same way, and Θ means both: the growth is tight. For example, 3n² + 5n + 2 is Θ(n²).
The example counts the operations of three loops directly. Halving n until it reaches 1 takes about log₂ n steps, one pass over n items takes n steps, and a loop nested inside a loop takes n × n steps. When n doubles, the logarithmic count grows by one, the linear count doubles, and the quadratic count quadruples. That behaviour, not the exact numbers, is what the notation describes.
Code example
def count_log(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
def count_linear(n):
steps = 0
for _ in range(n):
steps += 1
return steps
def count_quadratic(n):
steps = 0
for _ in range(n):
for _ in range(n):
steps += 1
return steps
for n in (8, 16, 32):
print(n, count_log(n), count_linear(n), count_quadratic(n))
assert count_log(1024) == 108 3 8 64 16 4 16 256 32 5 32 1024
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
def count_log(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps def count_linear(n): steps = 0 for _ in range(n): steps += 1 return steps def count_quadratic(n): steps = 0 for _ in range(n): for _ in range(n): steps += 1 return steps for n in (8, 16, 32): print(n, count_log(n), count_linear(n), count_quadratic(n))assert count_log(1024) == 10Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Each pass halves n, so 8 reaches 1 after 3 halvings: 8, 4, 2, 1. | n: 8 → 4 → 2 → 1 | — | |
| The linear loop touches each of the n items once, so it counts exactly n. | count_linear(8) = 8 | — | |
| The inner statement runs once for every pair of loop positions: n × n times. | count_quadratic(8) = 64 | — | |
| Doubling n adds 1 to the log count, doubles the linear count, and quadruples the quadratic count. | count_quadratic(8) = 64 | 8 3 8 64 16 4 16 256 32 5 32 1024 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
count_log is Θ(log n), count_linear is Θ(n), and count_quadratic is Θ(n²) time. All three use O(1) extra space.
- Big O is an upper bound, not a synonym for worst case. A worst-case running time and an upper bound on it are different ideas; this lesson uses Θ because the counts are tight.
- Dropping constants hides real cost for small inputs. An O(n) algorithm with a large constant can lose to an O(n²) algorithm on small n.
- log n has no base in asymptotic notation because changing the base multiplies by a constant, but the exact counts above do depend on using base 2.
Try it yourself
Predict count_log(64), count_linear(64), and count_quadratic(64).
Reveal answer and reasoning
6, 64, and 4096. 64 is 2⁶, so six halvings reach 1; the other counts are n and n².