DSA Reading Growth Tables

A growth table lists step counts for the main Big O classes at growing values of n. The numbers show how quickly each class pulls away from the others.

Log n beside n and n squared

Log n counts the halvings that shrink n down to one. The int call drops each fraction, and the columns are n, log n, n, and n squared.

import math

print("n", "log n", "n", "n squared")
for n in [10, 20, 40]:
    print(n, int(math.log2(n)), n, n * n)

The power class explodes

Each added item doubles the 2^n count. Twenty items already pass a million steps.

for n in [5, 10, 15, 20]:
    print(n, 2 ** n)

n log n sits between

The three numbers after n are n, n log n, and n squared. The middle column grows a little faster than n and far slower than n squared.

import math

for n in [10, 20]:
    print(n, n, n * int(math.log2(n)), n * n)

Example

import math

print("n | log n | n | n log n | n^2 | 2^n")
for n in [1, 2, 4, 8, 10, 16, 20]:
    log_n = int(math.log2(n)) if n > 1 else 0
    print(n, "|", log_n, "|", n, "|", n * log_n, "|", n * n, "|", 2 ** n)
print("Warning: 2^n at n = 30 is already", 2 ** 30, "steps")

Key points

A growth table turns Big O labels into numbers that can be compared directly
Log n: how many times n can be halved before it reaches one
2^n: two multiplied by itself n times, doubling with each added item
n log n: n multiplied by log n, a class between n and n squared

In this example, one loop prints a row for each chosen value of n. The log n column creeps from 0 to 4 across the whole table. The n squared column reaches 400 at n = 20. The 2^n column passes a million at the same row. The warning row extends that column to n = 30, where the count passes a billion.

Note

Tables in this course cap the 2^n column early, because its numbers outgrow the page.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

import math

print("n | log n | n | n log n | n^2 | 2^n")
for n in [1, 2, 4, 8, 10, 16, 20]:
    log_n = int(math.log2(n)) if n > 1 else 0
    print(n, "|", log_n, "|", n, "|", n * log_n, "|", n * n, "|", 2 ** n)
print("Warning: 2^n at n = 30 is already", 2 ** 30, "steps")

Exercise

At n = 20, which class needs about a million steps?

log n n log n n^2 2^n