← Practice
Lesson

Complexity

Learn the two ideas separately. Start with how much work the code does, then learn how much extra memory it uses.

Space →
Complexity · Work

Time Complexity

How does the amount of work grow as the input gets bigger? Let n mean the input size.

Basics

x = nums[0]                 # O(1)

for x in nums:              # O(n)
    ...

for x in nums:              # O(n²)
    for y in nums:
        ...

Quick rule: one lookup → O(1), one full scan → O(n), nested full scans → O(n²).

Ignore constants and smaller terms: O(2n) → O(n), O(n + 10) → O(n), O(n² + n) → O(n²).

Function calls

A function call is not automatically O(1). Include the work inside it.

nums.sort()                 # O(n log n)

One after another → add

helper(nums)                # O(n)
helper(nums)                # O(n)
# O(n) + O(n) = O(n)

Repeated inside a loop → multiply

for x in nums:              # n times
    helper(nums)            # O(n) each
# n × n = O(n²)
Remember: sequential → add. Nested/repeated → multiply. Keep the fastest-growing term.

Recursion

Ask: How many calls are made, and how much work does each call do?

def countdown(n: int):
    if n == 0:
        return
    countdown(n - 1)
# one chain of n calls → O(n)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
# branching calls → exponential time

Without memoization, Fibonacci repeatedly solves the same smaller problems. O(2ⁿ) is a useful simple upper bound.

Dynamic programming

DP avoids recalculating the same smaller problems.

ApproachTime
Plain branching recursionO(2ⁿ)
MemoizationO(n)
1D DPO(n)
Rolling variablesO(n)

Why exponential gets bad quickly

nO(n)O(n²)O(2ⁿ)
10101001,024
20204001,048,576
50502,500> 1 quadrillion
Time checklist: What work repeats? Include the cost of called functions. Sequential work adds; repeated or nested work multiplies.
Time →
Complexity · Memory

Auxiliary Space

How much extra working memory grows with the input? Here, required input and required output are excluded.

Basics

count = 0
for x in nums:
    if x > 0:
        count += 1
# fixed variables → O(1)
seen = set()
for x in nums:
    seen.add(x)
# extra set can grow to n → O(n)
Quick rule: fixed variables → O(1). Extra list, set, or dict growing with n → O(n).

Required output vs temporary memory

def keep_evens(nums: list[int]) -> list[int]:
    result = []
    for x in nums:
        if x % 2 == 0:
            result.append(x)
    return result

Output: O(n). The required returned result is not counted in our Auxiliary Space.

temp = nums.copy()
return temp[0]
# temp is working memory → O(n) auxiliary space

In an interview, be explicit: “O(1) auxiliary space, excluding required input/output.”

Recursion

Count the maximum calls alive at the same time, not the total number of calls.

def countdown(n: int):
    if n == 0:
        return
    countdown(n - 1)
# stack depth n → O(n) auxiliary space

Naive Fibonacci can take exponential time but still has only O(n) maximum recursion depth.

Dynamic programming

dp = [0] * (n + 1)
# n-sized working table → O(n)

If each state only needs a few previous states:

prev2 = 1
prev1 = 1
for i in range(2, n + 1):
    current = prev1 + prev2
    prev2 = prev1
    prev1 = current
# fixed variables → O(1)

The auxiliary space drops from O(n) to O(1).

Auxiliary-space checklist: What extra working memory grows? Count temporary structures and recursion stack. Exclude required input/output.