⏱️ Time & Space Complexity

Beginner ~25 min read

Your API got sluggish after users doubled — is the culprit an O(n²) loop or a costly data structure? In this lesson, you'll learn Big O notation — the universal language for describing algorithm performance — and how to analyze both time and space complexity so you can diagnose and fix issues like this with confidence.

This builds on your foundation from the introduction.

⚠️ The Startup That Almost Died

Day 1: Sarah launches her photo-sharing app. 100 users. Everything works perfectly. Response time: 50ms. ✅

Day 30: App goes viral! 10,000 users. Suddenly, loading photos takes 5 seconds. Users complain. Servers crash. 💥

The Problem: Sarah's code checked every user against every other user to find mutual friends. That's O(n²)!

The Fix: A senior developer rewrote it using a hash table. Same feature, O(n) complexity. Response time back to 50ms. Company saved. 🎉

The Lesson: Big O isn't academic theory—it's the difference between a successful app and a failed startup.

How Algorithms Scale: Sarah's App

❌ O(n²) - Original Code

100 users = 0.05s
10,000 users = 5s 💥
Exponential growth kills scalability

✅ O(n) - After Fix

100 users = 0.05s
10,000 users = 0.08s ✅
Linear growth is manageable

🚀 O(1) - Best Case

100 users = 0.05s
10,000 users = 0.05s 🎉
Constant time, infinite scale

The takeaway: Algorithm choice determines whether your app scales to millions or crashes at thousands.

What is Time Complexity?

Time complexity measures how the runtime of an algorithm grows as the input size increases. It's not about measuring exact seconds - it's about understanding the growth rate.

📚 Real-World Analogy

Imagine you're looking for a book in a library:

Method 1: Check every shelf one by one (slow, grows with library size)
Method 2: Use the catalog system (fast, doesn't grow much with library size)

Time complexity helps us compare these methods mathematically!

Why Time Complexity Matters

Scalability: Will your code work with 1 million users? 1 billion?
Performance: Avoid slow algorithms that frustrate users
Resource Costs: Faster algorithms = lower server costs
Interviews: Every tech interview asks about Big O!

Big O Notation Explained

Big O notation describes the worst-case growth rate of an algorithm. It answers: "How does runtime change when input size doubles?"

🎯 Key Principle

Big O focuses on the dominant term and ignores constants:

3n + 5 → O(n) (drop constants)
n² + 100n + 50 → O(n²) (n² dominates)
5 → O(1) (constant)

Quick Quiz: Drop What Doesn’t Matter

Apply the Big O rules to simplify these. Reveal to check yourself.

7n + 3

Show answer
Drop constants → O(n)
n² + 50n + 500

Show answer
n² dominates → O(n²)
n log n + n

Show answer
n log n dominates → O(n log n)

Big O Growth Comparison

See how different complexities grow as input size increases. Play the animation to watch the curves grow!

Pro Tip: Use the slider to see exact operation counts at different input sizes. Notice how O(2ⁿ) explodes while O(1) stays flat!

Analogy Check: Library Search

Checking every shelf is like O(n); using the catalog to jump to the right shelf is like O(log n). As your library (n) grows, the difference becomes dramatic.

Common Complexity Classes

You'll explore each complexity class with real code you can run.

Quick Quiz: Classify Code

Pick the Big O for each snippet. Reveal to check.

def has_value(arr, x):
    for v in arr:
        if v == x:
            return True
    return False

Show answer

Worst case scans all elements → O(n)

def pairs(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i):
            _ = arr[i] + arr[j]

Show answer

Triangular nested loop → about n(n-1)/2 steps → O(n²)

def shrink(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

Show answer

Halving each step → O(log n)

1. O(1) - Constant Time ⚡

Operations that take the same time regardless of input size.

Output

Click Run to execute your code

Examples of O(1):

Array access by index: arr[5]
Hash table lookup: dict[key]
Push/pop from stack
Simple arithmetic operations

2. O(log n) - Logarithmic Time 🚀

Algorithms that halve the problem size each step. Very efficient!

# O(log n) - Logarithmic Time Example
# Binary search - halves the search space each time

def binary_search(arr, target):
    """Binary search with operation counting"""
    left, right = 0, len(arr) - 1
    operations = 0
    
    while left <= right:
        operations += 1
        mid = (left + right) // 2
        
        print(f"Step {operations}: Checking index {mid}, value = {arr[mid]}")
        
        if arr[mid] == target:
            print(f"✅ Found {target} at index {mid}")
            print(f"Total operations: {operations}")
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    print(f"❌ {target} not found")
    print(f"Total operations: {operations}")
    return -1

# Test with sorted array
arr = list(range(1, 101))  # [1, 2, 3, ..., 100]
target = 67

print("O(log n) - Logarithmic Time")
print("=" * 40)
print(f"Searching for {target} in array of {len(arr)} elements\n")

binary_search(arr, target)

import math
print(f"\n✅ Time complexity: O(log n)")
print(f"Max operations for n={len(arr)}: {math.ceil(math.log2(len(arr)))}")
print(f"For n=1,000,000: only ~20 operations!")

Output

Click Run to execute your code

Examples of O(log n):

Binary search on sorted array
Balanced binary search tree operations
Finding power of a number (divide and conquer)

3. O(n) - Linear Time 📈

Runtime grows proportionally with input size.

# O(n) - Linear Time Example
# Must check every element once

def find_max(arr):
    """Find maximum element - must check all elements"""
    if not arr:
        return None
    
    max_val = arr[0]
    operations = 0
    
    for num in arr:
        operations += 1
        if num > max_val:
            max_val = num
    
    print(f"Found maximum: {max_val}")
    print(f"Operations: {operations}")
    return max_val

def linear_search(arr, target):
    """Search for element - worst case checks all"""
    operations = 0
    
    for i, num in enumerate(arr):
        operations += 1
        if num == target:
            print(f"✅ Found {target} at index {i}")
            print(f"Operations: {operations}")
            return i
    
    print(f"❌ {target} not found")
    print(f"Operations: {operations}")
    return -1

# Test
arr = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50]

print("O(n) - Linear Time")
print("=" * 40)
print(f"Array: {arr}\n")

print("Finding maximum:")
find_max(arr)

print("\nSearching for 90:")
linear_search(arr, 90)

print(f"\n✅ Time complexity: O(n)")
print(f"Operations: {len(arr)} (checks every element)")

Output

Click Run to execute your code

Examples of O(n):

Linear search through array
Finding min/max in unsorted array
Counting elements
Printing all elements

4. O(n log n) - Linearithmic Time ⚙️

Common in efficient sorting algorithms.

# O(n log n) - Linearithmic Time Example
# Merge sort - efficient sorting algorithm

def merge_sort(arr, depth=0):
    """Merge sort with operation tracking"""
    if len(arr) <= 1:
        return arr, 0
    
    # Divide
    mid = len(arr) // 2
    left, left_ops = merge_sort(arr[:mid], depth + 1)
    right, right_ops = merge_sort(arr[mid:], depth + 1)
    
    # Conquer (merge)
    merged, merge_ops = merge(left, right)
    
    total_ops = left_ops + right_ops + merge_ops
    
    if depth == 0:
        print(f"Total operations: {total_ops}")
    
    return merged, total_ops

def merge(left, right):
    """Merge two sorted arrays"""
    result = []
    i = j = ops = 0
    
    while i < len(left) and j < len(right):
        ops += 1
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result, ops

# Test
arr = [64, 34, 25, 12, 22, 11, 90, 88]

print("O(n log n) - Linearithmic Time")
print("=" * 40)
print(f"Original array: {arr}")
print(f"Array size: {len(arr)}\n")

sorted_arr, operations = merge_sort(arr.copy())

print(f"Sorted array: {sorted_arr}")

import math
expected = len(arr) * math.log2(len(arr))
print(f"\n✅ Time complexity: O(n log n)")
print(f"Expected operations: ~{int(expected)}")
print(f"Actual operations: {operations}")

Output

Click Run to execute your code

Examples of O(n log n):

Merge sort
Quick sort (average case)
Heap sort
Sorting is often the bottleneck!

5. O(n²) - Quadratic Time 🐌

Nested loops over the input. Gets slow quickly!

# O(n²) - Quadratic Time Example
# Bubble sort - nested loops over the array

def bubble_sort(arr):
    """Bubble sort with operation counting"""
    n = len(arr)
    operations = 0
    
    for i in range(n - 1):
        for j in range(n - i - 1):
            operations += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    print(f"Total operations: {operations}")
    return arr, operations

def has_duplicate(arr):
    """Check for duplicates - naive approach"""
    operations = 0
    
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            operations += 1
            if arr[i] == arr[j]:
                print(f"✅ Found duplicate: {arr[i]}")
                print(f"Operations: {operations}")
                return True
    
    print(f"❌ No duplicates found")
    print(f"Operations: {operations}")
    return False

# Test
arr = [64, 34, 25, 12, 22, 11, 90, 88]

print("O(n²) - Quadratic Time")
print("=" * 40)
print(f"Original array: {arr}")
print(f"Array size: {len(arr)}\n")

print("Bubble Sort:")
sorted_arr, ops = bubble_sort(arr.copy())
print(f"Sorted: {sorted_arr}\n")

print("Checking for duplicates:")
has_duplicate([1, 2, 3, 4, 5])

expected = len(arr) ** 2
print(f"\n✅ Time complexity: O(n²)")
print(f"For n={len(arr)}: ~{expected} operations")
print(f"For n=100: ~10,000 operations")
print(f"For n=1000: ~1,000,000 operations!")

Output

Click Run to execute your code

Caution: O(n²) algorithms are acceptable for small inputs (n < 1000) but become impractical for large datasets. Always look for better alternatives!

Examples of O(n²):

Bubble sort, Selection sort, Insertion sort
Checking all pairs in an array
Naive duplicate detection

6. O(2ⁿ) - Exponential Time 💥

Doubles with each additional input. Avoid if possible!

# O(2ⁿ) - Exponential Time Example
# Fibonacci with naive recursion - VERY SLOW!

call_count = 0

def fibonacci_recursive(n):
    """Naive recursive Fibonacci - exponential time!"""
    global call_count
    call_count += 1
    
    if n <= 1:
        return n
    
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

def fibonacci_optimized(n, memo={}):
    """Optimized with memoization - much faster!"""
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci_optimized(n - 1, memo) + fibonacci_optimized(n - 2, memo)
    return memo[n]

# Test
print("O(2ⁿ) - Exponential Time")
print("=" * 40)

# Small input - already slow!
n = 10
call_count = 0
result = fibonacci_recursive(n)
print(f"Fibonacci({n}) = {result}")
print(f"Function calls: {call_count}")
print(f"Expected ~2^{n} = {2**n} operations\n")

# Larger input
n = 20
call_count = 0
result = fibonacci_recursive(n)
print(f"Fibonacci({n}) = {result}")
print(f"Function calls: {call_count}")
print(f"Expected ~2^{n} = {2**n:,} operations\n")

print("⚠️ WARNING: Don't try n=30+ with naive recursion!")
print("It would take millions of operations!\n")

# Show optimized version
print("With optimization (memoization):")
result = fibonacci_optimized(50)
print(f"Fibonacci(50) = {result}")
print("✅ Runs instantly!\n")

print("✅ Time complexity: O(2ⁿ)")
print("This is why algorithm choice matters!")

Output

Click Run to execute your code

Warning: O(2ⁿ) algorithms are only practical for very small inputs (n < 20). They're often a sign that optimization is needed!

Complexity Comparison Table

Here's how different complexities scale with input size:

Complexity	n=10	n=100	n=1,000	n=10,000
O(1)	1	1	1	1
O(log n)	3	7	10	13
O(n)	10	100	1,000	10,000
O(n log n)	30	664	9,966	132,877
O(n²)	100	10,000	1,000,000	100,000,000
O(2ⁿ)	1,024	1.27×10³⁰	∞	∞

Key Insight: Notice how O(2ⁿ) becomes impossible even for n=100! This is why algorithm choice is critical for scalability.

Space Complexity

Space complexity measures how much extra memory an algorithm uses as input size grows. It doesn't count the input itself, only additional space needed.

O(1) Space - In-Place Algorithms

Uses constant extra space regardless of input size:

# Space Complexity: O(1) - In-Place Algorithm
# Uses constant extra space regardless of input size

def reverse_array_inplace(arr):
    """Reverse array in-place - O(1) space"""
    left = 0
    right = len(arr) - 1
    
    while left < right:
        # Swap elements
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    
    return arr

def find_max_inplace(arr):
    """Find max without extra array - O(1) space"""
    max_val = arr[0]
    
    for num in arr:
        if num > max_val:
            max_val = num
    
    return max_val

# Test
arr = [64, 34, 25, 12, 22, 11, 90, 88]

print("Space Complexity: O(1) - In-Place")
print("=" * 40)
print(f"Original array: {arr}\n")

# Reverse in-place
arr_copy = arr.copy()
reversed_arr = reverse_array_inplace(arr_copy)
print(f"Reversed (in-place): {reversed_arr}")

# Find max
max_val = find_max_inplace(arr)
print(f"Maximum value: {max_val}")

print("\n✅ Space complexity: O(1)")
print("Only uses a few variables (left, right, max_val)")
print("No extra arrays or data structures created")
print("Space usage doesn't grow with input size!")

Output

Click Run to execute your code

O(n) Space - Extra Data Structures

Creates new arrays, lists, or hash maps proportional to input:

# Space Complexity: O(n) - Extra Space
# Creates new data structures proportional to input size

def reverse_array_copy(arr):
    """Reverse array by creating new array - O(n) space"""
    reversed_arr = []
    
    for i in range(len(arr) - 1, -1, -1):
        reversed_arr.append(arr[i])
    
    return reversed_arr

def filter_even_numbers(arr):
    """Create new array with even numbers - O(n) space"""
    even_numbers = []
    
    for num in arr:
        if num % 2 == 0:
            even_numbers.append(num)
    
    return even_numbers

def create_frequency_map(arr):
    """Create hash map of frequencies - O(n) space"""
    frequency = {}
    
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    
    return frequency

# Test
arr = [64, 34, 25, 12, 22, 11, 90, 88, 34, 22]

print("Space Complexity: O(n) - Extra Space")
print("=" * 40)
print(f"Original array: {arr}")
print(f"Array size: {len(arr)}\n")

# Reverse with copy
reversed_arr = reverse_array_copy(arr)
print(f"Reversed (new array): {reversed_arr}")
print(f"Extra space: {len(reversed_arr)} elements\n")

# Filter evens
even_nums = filter_even_numbers(arr)
print(f"Even numbers: {even_nums}")
print(f"Extra space: {len(even_nums)} elements\n")

# Frequency map
freq_map = create_frequency_map(arr)
print(f"Frequency map: {freq_map}")
print(f"Extra space: {len(freq_map)} entries\n")

print("✅ Space complexity: O(n)")
print("Creates new data structures")
print("Space usage grows with input size")
print(f"For n={len(arr)}: uses ~{len(arr)} extra space")

Output

Click Run to execute your code

Time vs Space Tradeoff

Often you can trade time for space or vice versa:

Hash tables: Use O(n) space to get O(1) lookup time
Memoization: Store results (O(n) space) to avoid recomputation
In-place sorting: Save space but may be slower

How to Calculate Complexity

Rule 1: Drop Constants

# O(2n) → O(n)
for i in range(n):
    print(i)
for i in range(n):
    print(i)

# Both loops are O(n), total is O(2n) = O(n)

Rule 2: Drop Non-Dominant Terms

# O(n² + n) → O(n²)
for i in range(n):
    for j in range(n):
        print(i, j)  # O(n²)

for i in range(n):
    print(i)  # O(n)

# n² dominates n, so total is O(n²)

Rule 3: Different Inputs = Different Variables

# O(a + b), NOT O(n)
for i in range(len(a)):
    print(a[i])

for j in range(len(b)):
    print(b[j])

Rule 4: Nested Loops = Multiply

# O(n × m)
for i in range(n):
    for j in range(m):
        print(i, j)

Quick Reference:

Single loop → O(n)
Nested loops → O(n²), O(n³), etc.
Halving input → O(log n)
Recursion → Draw recursion tree

Common Mistakes

❌ Mistake 1: Confusing O(n) with O(2n)

# Wrong: "This is O(2n)"
for i in range(n):
    print(i)
for i in range(n):
    print(i)

# Correct: O(2n) = O(n)
# Constants are dropped in Big O!

❌ Mistake 2: Ignoring Best/Average/Worst Cases

# Quick Sort:
# Best case: O(n log n)
# Average case: O(n log n)
# Worst case: O(n²)  ← Big O refers to worst case!

# Always specify which case you're analyzing

❌ Mistake 3: Forgetting Space Complexity

# This is O(n) time AND O(n) space!
def create_copy(arr):
    new_arr = []
    for item in arr:
        new_arr.append(item)
    return new_arr

# Always consider both time AND space!

Exercise: Analyze Complexity

Task: Determine the time complexity of each function below.

# Exercise: Analyze Time Complexity
# Determine the Big O complexity of each function

# Function 1
def function1(arr):
    """What is the time complexity?"""
    return arr[0] + arr[-1]

# Function 2
def function2(arr):
    """What is the time complexity?"""
    total = 0
    for num in arr:
        total += num
    return total

# Function 3
def function3(arr):
    """What is the time complexity?"""
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i] + arr[j])

# Function 4
def function4(arr, target):
    """What is the time complexity?"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Function 5
def function5(n):
    """What is the time complexity?"""
    if n <= 1:
        return n
    return function5(n - 1) + function5(n - 2)

# Test your understanding
print("Analyze the time complexity of each function:")
print("=" * 50)
print("\nFunction 1: Accesses first and last element")
print("Your answer: ___________")

print("\nFunction 2: Sums all elements")
print("Your answer: ___________")

print("\nFunction 3: Nested loops over array")
print("Your answer: ___________")

print("\nFunction 4: Binary search")
print("Your answer: ___________")

print("\nFunction 5: Recursive Fibonacci")
print("Your answer: ___________")

print("\n" + "=" * 50)
print("Uncomment the solutions below to check your answers!")
print("=" * 50)

# SOLUTIONS (uncomment to reveal)
# print("\nSOLUTIONS:")
# print("Function 1: O(1) - Constant time, just two array accesses")
# print("Function 2: O(n) - Linear time, loops through all elements")
# print("Function 3: O(n²) - Quadratic time, nested loops")
# print("Function 4: O(log n) - Logarithmic time, binary search")
# print("Function 5: O(2ⁿ) - Exponential time, naive recursion")

Output

Click Run to execute your code

💡 Show Solutions

Function 1: O(1) - Just two array accesses, constant time
Function 2: O(n) - Single loop through all elements
Function 3: O(n²) - Nested loops, both iterate n times
Function 4: O(log n) - Binary search, halves search space
Function 5: O(2ⁿ) - Naive Fibonacci, exponential recursion

Summary

Big O Notation: Describes worst-case growth rate of algorithms
Common Classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
Drop Constants: O(2n) = O(n), O(n + 5) = O(n)
Dominant Terms: O(n² + n) = O(n²)
Space Complexity: Measure extra memory used
Tradeoffs: Often can trade time for space or vice versa
Analysis Rules: Loops multiply, sequential operations add

Bring it back to reality: If users double and your endpoint slows, Big O helps you reason about where the time goes — aim for O(n log n) solutions over O(n²) when scaling. In interviews, explain the tradeoffs clearly.

What's Next?

Now that you understand how to analyze algorithm efficiency, you're ready to dive into actual algorithms! In the next lesson, we'll explore Algorithm Analysis Techniques including recurrence relations and the Master Theorem for analyzing recursive algorithms.

Practice Tip: For every algorithm you learn from now on, always ask: "What's the time complexity? What's the space complexity?" This habit will make you a better programmer!

Previous Why DSA Matters

Next Algorithm Analysis

⚠️ The Startup That Almost Died

How Algorithms Scale: Sarah's App

What is Time Complexity?

📚 Real-World Analogy

Why Time Complexity Matters

Big O Notation Explained

🎯 Key Principle

Quick Quiz: Drop What Doesn’t Matter

Big O Growth Comparison

Analogy Check: Library Search

Common Complexity Classes

Quick Quiz: Classify Code

1. O(1) - Constant Time ⚡

2. O(log n) - Logarithmic Time 🚀

3. O(n) - Linear Time 📈

4. O(n log n) - Linearithmic Time ⚙️

5. O(n²) - Quadratic Time 🐌

6. O(2ⁿ) - Exponential Time 💥

Complexity Comparison Table

Space Complexity

O(1) Space - In-Place Algorithms

O(n) Space - Extra Data Structures

Time vs Space Tradeoff

How to Calculate Complexity

Rule 1: Drop Constants

Rule 2: Drop Non-Dominant Terms

Rule 3: Different Inputs = Different Variables

Rule 4: Nested Loops = Multiply

Common Mistakes

❌ Mistake 1: Confusing O(n) with O(2n)

❌ Mistake 2: Ignoring Best/Average/Worst Cases

❌ Mistake 3: Forgetting Space Complexity

Exercise: Analyze Complexity

Summary

What's Next?

Enjoying these tutorials?