Time and Space Complexity

What Big-O tells you

Big-O ignores exact timings and constants and asks: when the input size n doubles, what happens to the work? It describes the shape of the growth.

Notation	Name	Doubling the input…	Example
O(1)	Constant	does not change the work	Look up a key in a hash map
O(log n)	Logarithmic	adds one small step	Binary search in a sorted list
O(n)	Linear	doubles the work	Scan a list once
O(n log n)	Linearithmic	slightly more than doubles it	Efficient sorting
O(n squared)	Quadratic	quadruples the work	Compare every item with every other

Time and space

Time complexity is how the number of steps grows, and space complexity is how the memory used grows. They often trade against each other: a lookup table or cache spends memory to save time. See Data Structures.

Spotting it in code

# Python
for a in items:          # n times
    for b in items:      # n times for each a: O(n squared)
        compare(a, b)

x in some_list           # scans the list: O(n)
x in some_set            # hash lookup: O(1) on average

• A single loop over the data is usually O(n); a loop inside a loop over the same data, O(n squared).
• Calling something that itself loops (a “contains” on a list, a database query) inside a loop multiplies the cost.
• Halving the problem at each step suggests O(log n).

Keep it in proportion

• It matters when n is large or growing. For ten items, the simplest readable code wins.
• Big-O hides constants, so measure before you rewrite; see Performance Basics.

Try it

Write a function that finds the items two lists have in common, first with nested loops, then by turning one list into a set. Time both with 1,000, 10,000 and 100,000 items.