Growth rates and asymptotic notation

Count operations to see how logarithmic, linear, and quadratic work grow with input size.

Python

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) == 10

Output

8 3 8 64
16 4 16 256
32 5 32 1024

Explanation

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.

Explore the dry run

Guided walkthroughReady

1def count_log(n):

2 steps = 0

3 while n > 1:

4 n //= 2

5 steps += 1

6 return steps

9def count_linear(n):

10 steps = 0

11 for _ in range(n):

12 steps += 1

13 return steps

16def count_quadratic(n):

17 steps = 0

18 for _ in range(n):

19 for _ in range(n):

20 steps += 1

21 return steps

24for n in (8, 16, 32):

25 print(n, count_log(n), count_linear(n), count_quadratic(n))

26assert count_log(1024) == 10

Follow 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

Prepared trace of the published program. Some rows group repeated iterations.
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

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².

Growth rates and asymptotic notation

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading