When you see a piece of code, can you determine its time and space complexity? This tutorial will teach you a systematic approach to analyze any algorithm.

Goal: By the end of this tutorial, you'll be able to look at any code and determine its complexity in seconds.

Key Skill: Analyzing code complexity is essential for technical interviews, optimizing performance, and writing efficient algorithms.

The Step-by-Step Analysis Method

Follow this process for every code analysis:

Step 1: Identify the Input Size

Question: What is 'n' in this problem?

Common patterns:

›Array/list length
›String length
›Number value
›Matrix dimensions (m × n)
›Tree height
›Graph vertices/edges

Step 2: Count the Operations

Look for:

›Loops (for, while)
›Recursive calls
›Nested structures
›Data structure operations

Step 3: Express as Mathematical Function

Convert to:

›Single loop → n
›Nested loops → n²
›Recursive calls → depends on recursion tree
›Halving each time → log n

Step 4: Simplify Using Big-O Rules

Rules:

›Drop constants: O(3n) → O(n)
›Drop non-dominant terms: O(n² + n) → O(n²)
›Different variables: O(a + b) stays as O(a + b)

Step 5: Determine Space Complexity

Count:

›Extra arrays/lists created
›Recursion call stack depth
›Hash maps/sets
›Variables (usually O(1))

Example 1: Simple Loop

Let's analyze this code step-by-step:

Python

def print_numbers(n):
    for i in range(n):
        print(i)

Analysis:

Step 1 - Input size: n (the parameter)

Step 2 - Operations:

›Loop runs from 0 to n-1
›Total iterations: n
›Each iteration: 1 print operation

Step 3 - Mathematical expression:

›f(n) = n iterations × 1 operation = n

Step 4 - Big-O simplification:

›Time Complexity: O(n)

Step 5 - Space complexity:

›Variables: i (constant)
›Space Complexity: O(1)

Answer: Time O(n), Space O(1)

Example 2: Nested Loops

Python

def print_pairs(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

Analysis:

Step 1: Input size = n

Step 2: Operations count

›Outer loop: n iterations
›Inner loop: n iterations (for each outer iteration)
›Total: n × n = n²

Step 3: f(n) = n²

Step 4: Time Complexity: O(n²)

Step 5: Space: Only variables i, j → O(1)

Answer: Time O(n²), Space O(1)

Example 3: Sequential Loops

Python

def two_loops(arr):
    # First loop
    for i in range(len(arr)):
        print(arr[i])
    
    # Second loop
    for i in range(len(arr)):
        print(arr[i] * 2)

Analysis:

Step 1: Input size = n (array length)

Step 2: Operations

›First loop: n iterations
›Second loop: n iterations
›Total: n + n = 2n

Step 3: f(n) = 2n

Step 4: Drop constant: O(2n) → O(n)

Step 5: Space: O(1)

Answer: Time O(n), Space O(1)

Key Point: Sequential loops add, not multiply: O(n + n) = O(n)

Example 4: Different Input Sizes

Python

def process_two_arrays(arr1, arr2):
    for item in arr1:
        print(item)
    
    for item in arr2:
        print(item)

Analysis:

Step 1: Two input sizes: a = len(arr1), b = len(arr2)

Step 2: Operations

›First loop: a iterations
›Second loop: b iterations
›Total: a + b

Step 3: f(a, b) = a + b

Step 4: Cannot simplify - different variables!

Answer: Time O(a + b), Space O(1)

Important: Don't write O(n) when you have different input sizes!

Example 5: Halving the Input

Python

def binary_search(arr, target):
    left = 0
    right = 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

Analysis:

Step 1: Input size = n (array length)

Step 2: Operations

›Each iteration: search space halves
›n → n/2 → n/4 → n/8 → ... → 1
›How many times can you divide n by 2? log₂(n)

Step 3: f(n) = log₂(n)

Step 4: Time Complexity: O(log n)

Step 5: Space: Variables only → O(1)

Answer: Time O(log n), Space O(1)

Pattern: Halving input size each time = O(log n)

Example 6: Recursion - Linear

Python

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Call tree:
# factorial(5)
#   → factorial(4)
#     → factorial(3)
#       → factorial(2)
#         → factorial(1)

Analysis:

Step 1: Input size = n

Step 2: Recursion tree

›factorial(n) → factorial(n-1) → ... → factorial(1)
›Depth: n levels
›Work per level: O(1) multiplication

Step 3: f(n) = n levels × 1 work = n

Step 4: Time: O(n)

Step 5: Space: Call stack depth = n → O(n)

Answer: Time O(n), Space O(n)

Key Point: Recursion uses space for the call stack!

Example 7: Recursion - Binary Tree

Python

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Call tree for fib(5):
#              fib(5)
#            /        \
#        fib(4)      fib(3)
#       /    \       /    \
#   fib(3) fib(2) fib(2) fib(1)
#   ...

Analysis:

Step 1: Input size = n

Step 2: Recursion tree

›Each call makes 2 recursive calls
›Height: n
›Total nodes: 2⁰ + 2¹ + 2² + ... + 2ⁿ ≈ 2ⁿ

Step 3: f(n) ≈ 2ⁿ

Step 4: Time: O(2ⁿ) - Exponential! Very slow!

Step 5: Space: Maximum call stack depth = n → O(n)

Answer: Time O(2ⁿ), Space O(n)

Example 8: Creating New Arrays

Python

def reverse_array(arr):
    reversed_arr = []
    
    for i in range(len(arr) - 1, -1, -1):
        reversed_arr.append(arr[i])
    
    return reversed_arr

Analysis:

Time:

›Loop: n iterations
›Time: O(n)

Space:

›New array: size n
›Space: O(n)

Answer: Time O(n), Space O(n)

Example 9: Hash Map Operations

Python

def find_duplicates(arr):
    seen = set()
    duplicates = []
    
    for num in arr:
        if num in seen:
            duplicates.append(num)
        else:
            seen.add(num)
    
    return duplicates

Analysis:

Time:

›Loop: n iterations
›Hash set lookup/insert: O(1) average
›Total: n × 1 = O(n)

Space:

›Hash set: worst case n elements
›Duplicates list: worst case n elements
›Total: O(n)

Answer: Time O(n), Space O(n)

Key Point: Hash map operations are O(1) on average!

Example 10: Matrix Operations

Python

def print_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    
    for i in range(rows):
        for j in range(cols):
            print(matrix[i][j])

Analysis:

Step 1: Input sizes: m = rows, n = cols

Step 2: Operations

›Outer loop: m iterations
›Inner loop: n iterations (for each outer)
›Total: m × n

Step 3: f(m, n) = m × n

Step 4: Time: O(m × n) or O(n²) if square matrix

Step 5: Space: O(1)

Answer: Time O(m × n), Space O(1)

Common Complexity Patterns

Pattern 1: Single Loop

for i in range(n):
    # O(1) operations

Time: O(n)

Pattern 2: Nested Loops (Same Size)

for i in range(n):
    for j in range(n):
        # O(1) operations

Time: O(n²)

Pattern 3: Nested Loops (Different Sizes)

for i in range(m):
    for j in range(n):
        # O(1) operations

Time: O(m × n)

Pattern 4: Halving Each Time

while n > 1:
    n = n // 2

Time: O(log n)

Pattern 5: Two Branches Recursion

def recursive(n):
    if n <= 1:
        return
    recursive(n - 1)
    recursive(n - 1)

Time: O(2ⁿ)

Pattern 6: Divide and Conquer

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Time: O(n log n)

Practice Problems

Problem 1: Analyze This Code

Python

def mystery1(n):
    count = 0
    i = 1
    
    while i < n:
        count += 1
        i *= 2
    
    return count

Your Turn: What's the time and space complexity?

Answer:

›i doubles each time: 1 → 2 → 4 → 8 → ... → n
›How many times? log₂(n)
›Time: O(log n)
›Space: O(1)

Problem 2: Analyze This Code

Python

def mystery2(arr):
    result = []
    
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            result.append(arr[i] + arr[j])
    
    return result

Your Turn: What's the complexity?

Answer:

›Outer loop: n times
›
Inner loop: starts at i, goes to n
- ›i=0: n iterations
- ›i=1: n-1 iterations
- ›i=2: n-2 iterations
- ›Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
›Time: O(n²)
›Space: Result array has n² elements → O(n²)

Problem 3: Analyze This Code

Python

def mystery3(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mystery3(arr[:mid])
    right = mystery3(arr[mid:])
    
    return left + right

Your Turn: What's the complexity?

Answer:

›Divides array in half each level: log n levels
›Each level processes n elements
›Time: O(n log n)
›Space: Creates new arrays at each level → O(n log n)

Quick Reference Table

Code Pattern	Time	Space
Single loop	O(n)	O(1)
Two nested loops	O(n²)	O(1)
Three nested loops	O(n³)	O(1)
Binary search	O(log n)	O(1)
Merge sort	O(n log n)	O(n)
Quick sort (average)	O(n log n)	O(log n)
Linear recursion	O(n)	O(n)
Binary tree recursion	O(2ⁿ)	O(n)
Hash map lookup	O(1) avg	O(n)
Creating new array	O(n)	O(n)

Tips for Technical Interviews

Tip 1: State Your Assumptions

"I'm assuming the input is an array of length n..."

Tip 2: Walk Through Examples

"For n = 4, the loop runs 4 times..."

Tip 3: Explain Your Reasoning

"The outer loop runs n times, and for each iteration, the inner loop also runs n times, so that's n × n = n²"

Tip 4: Consider Best and Worst Cases

"In the best case when the element is first, it's O(1). In the worst case, it's O(n)."

Tip 5: Don't Forget Space Complexity

"Time is O(n) but we're also creating a new array, so space is O(n) too."

Common Mistakes to Avoid

Mistake 1: Forgetting Recursion Stack Space

Wrong: "This recursive function uses O(1) space"
Right: "O(n) space for the call stack"

Mistake 2: Confusing Sequential and Nested Loops

Wrong: Two loops = O(n²)
Right: Sequential = O(n + n) = O(n), Nested = O(n × n) = O(n²)

Mistake 3: Not Considering All Inputs

Wrong: "Time is O(n)"
Right: "Time is O(m × n) where m and n are different array sizes"

Mistake 4: Assuming Hash Operations Are Free

Wrong: "Hash map lookup is free, so O(1)"
Right: "Hash map lookup is O(1) average, but the space is O(n)"

Key Takeaways

Systematic approach: Follow the 5-step method for every analysis

Common patterns: Recognize loops, recursion, halving, and data structures

Multiple inputs: Use different variables (a, b, m, n) for different inputs

Don't forget space: Analyze both time and space complexity

Practice makes perfect: The more you analyze, the faster you'll get

Explain your reasoning: In interviews, talk through your thought process

What's Next?

Now that you can analyze code complexity:

›Arrays - Apply complexity analysis to array algorithms
›Sorting Algorithms - Analyze different sorting approaches
›Searching Algorithms - Compare search techniques

Final Practice Challenge

Analyze this complete algorithm:

Python

def challenge(arr):
    n = len(arr)
    result = []
    
    # Part 1: Nested loops
    for i in range(n):
        for j in range(i, n):
            if arr[i] + arr[j] > 10:
                result.append((i, j))
    
    # Part 2: Sort result
    result.sort()
    
    # Part 3: Binary search
    target = (0, 5)
    left, right = 0, len(result) - 1
    while left <= right:
        mid = (left + right) // 2
        if result[mid] == target:
            return mid
        elif result[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# What's the time and space complexity?

Answer:

›Part 1: O(n²) - nested loops
›Part 2: O(k log k) where k = size of result (worst case k = n²)
›Part 3: O(log k)
›Total Time: O(n²) + O(n² log n²) + O(log n²) = O(n² log n)
›Space: Result array stores up to n² pairs = O(n²)

Congratulations! You can now analyze any code's complexity. Keep practicing!

←

PreviousAsymptotic Notation

NextHow to Approach Problems

→