Time & Space Complexity

Time & Space Complexity | Algoryva

Worked by hand

Counting steps by hand

For each snippet, count the steps as a function of n, then simplify.

code shape	steps	Big-O	why
one statement, no loop	1	O(1)	does not depend on n
`for i in range(n)`	n	O(n)	one pass
loop inside a loop, both to n	n × n	O(n²)	every pair
loop where `i` doubles each time	about log₂ n	O(log n)	halving or doubling
loop of n containing a halving loop	n × log n	O(n log n)	multiply the nested costs
two loops one after the other	n + n = 2n	O(n)	add, then drop the constant
try every subset	2ⁿ	O(2ⁿ)	two choices per item

1
Read from the inside out
Find the innermost statement, ask how many times it runs in total, then simplify.
2
Loops that shrink or grow geometrically
If the loop variable doubles (i *= 2) or halves (n //= 2), the iteration count is log₂ n, not n.

Implementation

Measuring growth by counting operations

Instead of timing, count operations inside the code. The numbers below are exact and do not depend on the computer.

Plan in plain steps

pseudocode

linear: do 1 step per item
quadratic: do 1 step per pair of items
logarithmic: halve n until it reaches 1, count the halvings

python

def linear(n):
    ops = 0
    for _ in range(n):
        ops += 1
    return ops

def quadratic(n):
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1
    return ops

def halvings(n):
    ops = 0
    while n > 1:
        n //= 2
        ops += 1
    return ops

print(linear(10))   # 10
print(quadratic(10))   # 45
print(halvings(1024))   # 10
print(halvings(10**6))   # 19

Reading the code

›linear(n) counts exactly n. Double n and the count doubles.
›quadratic(n) counts the pairs (i, j) with i < j, which is n × (n − 1) / 2. For n = 10 that is 45. Double n and the count roughly quadruples.
›halvings(n) counts how many times you can halve n before reaching 1. A million needs only 19 halvings. That is why O(log n) is considered almost free.
›Notice we never needed a stopwatch: the growth rate is visible in the counts.

Implementation

Space complexity and the call stack

Space complexity counts the extra memory an algorithm needs *beyond the input*. A few variables are O(1). A new list of size n is O(n). Recursion also uses memory: every active call sits on the call stack, so a recursion that goes n levels deep uses O(n) space even if it creates no lists.

python

def sum_iter(a):          # O(1) extra space
    total = 0
    for x in a:
        total += x
    return total

def sum_copy(a):          # O(n) extra space: builds a new list
    prefix = []
    running = 0
    for x in a:
        running += x
        prefix.append(running)
    return prefix[-1]

def sum_rec(a, i=0):      # O(n) extra space: n stacked calls
    if i == len(a):
        return 0
    return a[i] + sum_rec(a, i + 1)

print(sum_iter([1, 2, 3, 4]))   # 10
print(sum_copy([1, 2, 3, 4]))   # 10
print(sum_rec([1, 2, 3, 4]))   # 10

Reading the code

›All three compute the same sum in O(n) time, but they use different memory.
›sum_iter keeps one number: O(1) space. sum_copy stores n prefix values: O(n). sum_rec makes n nested calls: O(n) stack space.
›Python allows about 1,000 nested calls by default, so sum_rec would crash on a list of 100,000 items even though the time would be fine.

Worked problem

Will this pass?

The problem

A problem has n up to 2 × 10⁵. Your first idea compares every pair of elements. Will it finish in about one second in Python? What complexity should you aim for?

Estimate the steps: n² = (2 × 10⁵)² = 4 × 10¹⁰.
Compare with the budget of about 10⁷ steps per second in Python (10⁸ in C++).
4 × 10¹⁰ is thousands of times too slow, so the pairwise idea cannot pass.
A target of O(n log n) is about 3.5 × 10⁶ steps, comfortably within budget: sort first, or use a dictionary.

python

import math

n = 2 * 10**5
quadratic = n * n
n_log_n = int(n * math.log2(n))
budget = 10**7

print(quadratic > budget)   # True
print(n_log_n < budget)   # True
print(quadratic // budget)   # 4000

Takeaway. Estimating the step count at the maximum n takes ten seconds and saves you from coding an idea that cannot pass. Do it before you write any code.

Worked problem

Find the complexity of a snippet

The problem

What is the time complexity of this code, and how many times does the inner statement run for n = 16?

The outer loop runs n times.
Inside, j starts at 1 and doubles while j < n. Doubling reaches n after log₂ n steps, so the inner loop is O(log n).
Nested, so multiply: O(n log n). For n = 16 the inner loop runs 4 times (j = 1, 2, 4, 8), so 16 × 4 = 64 times.

python

def count(n):
    c = 0
    for i in range(n):
        j = 1
        while j < n:
            c += 1
            j *= 2
    return c

print(count(16))   # 64
print(count(1024))   # 10240

Takeaway. Analyse loops from the inside out: find how often the inner body runs per outer step, then multiply. Doubling counters give logarithms.

Wrap-up

Remember this

Complexity describes how work grows with input size; stopwatches cannot predict that.
Count steps as a function of n, keep the fastest-growing term and drop constants.
Add sequential parts, multiply nested parts, and treat halving or doubling as logarithmic.
Space includes extra memory and recursion depth, not the input itself.
Read the constraints first: they tell you which complexity can pass.

Cheat sheet

Drop: constants and lower-order terms: 3n² + 5n → O(n²)
Add: sequential steps: O(n) + O(n²) = O(n²)
Multiply: nested steps: loop n × loop n = O(n²)
Halving / doubling: O(log n)
Budget: ≈ 10⁸ steps/s C++, ≈ 10⁷ Python
Pass guide: n=10⁵: n log n · n=5000: n² · n=20: 2ⁿ · n=10¹⁸: log n

Top traps to avoid

Counting every for loop as O(n) without checking the bounds.
Forgetting hidden loops in library calls (in, sort, slicing, sum, min).
Saying O(2n) or O(n + 5).

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the Big-O of 3n² + 50n + 7?
2.A loop does while n > 1: n //= 2. How many iterations for n = 1,000,000?
3.The statement says n ≤ 2 × 10⁵. Which complexity is the best target?
4.Why is x in some_list inside a loop over n items a danger?
5.How many times does the inner statement run? for i in range(n): for j in range(i + 1, n): ops += 1 with n = 6.
6.A recursive function calls itself n levels deep but creates no lists. What is its extra space?
7.For n = 1,000, roughly how many operations does an O(n log n) algorithm take?
8.What does O(1) time mean?
9.With n = 10⁶ and a 1-second limit in Python, which is most likely to pass?
10.For n = 4, how many times does the inner body of two nested loops over range(n) run?
11.For n = 100000, which is faster: O(n log n) or O(n²)?
12.What is the amortized cost of appending to a Python list?
13.Checking whether x is in a Python list of n items, in the worst case?
14.Checking whether x is in a Python set, on average?
15.Which of these is O(n log n) and common in contests?

Time & Space Complexity

After this lesson you will be able to

Builds on

Unlocks

Judging a route by turns, not by time of day

Just time it with a stopwatch

Count steps as a function of n, and look at the shape

Big-O in plain words

Why nested loops mean O(n²)

Why halving means O(log n)

Counting steps by hand

Measuring growth by counting operations

Reading the code

Space complexity and the call stack

Reading the code

A feel for how fast each class grows

Subtleties

Mistakes to avoid

Reading the constraints before you code

Will this pass?

Find the complexity of a snippet

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check