Practice: Analyzing Complexity of Code Snippets

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 5 Time to complete: ~25 minutes

Table of Contents

1. A Checklist for Analyzing Any Function
2. Worked Example 1: Two Independent Loops
3. Worked Example 2: A Loop with a Halving Step
4. Worked Example 3: A Hidden Nested Loop
5. Worked Example 4: Recursion
6. Common Traps to Watch For
7. Try It Yourself
8. Summary & Next Steps

1. A Checklist for Analyzing Any Function

1. Identify the input(s) and what n represents (list length? string length? tree nodes?).
2. Find every loop — is it a single pass, or nested inside another loop?
3. Check whether any loop's range shrinks (like halving) rather than staying proportional to n.
4. Check for function calls inside loops — does the called function have its own non-constant complexity?
5. Check for recursion — how many calls happen, and how deep does the stack go?
6. Combine using the rules from Chapter 3: sequential adds, nested multiplies, then keep only the dominant term.
7. Separately consider auxiliary space using Chapter 4's rules (new structures, recursion stack).

2. Worked Example 1: Two Independent Loops

def summary_stats(items):
    total = 0
    for item in items:          # Loop A: O(n)
        total += item
 
    maximum = items[0]
    for item in items:          # Loop B: O(n), NOT nested inside Loop A
        if item > maximum:
            maximum = item
 
    return total, maximum

Analysis: Loop A and Loop B are sequential, not nested → O(n) + O(n) = O(2n) → simplifies to O(n). Space: only a couple of scalar variables → O(1) auxiliary space.

3. Worked Example 2: A Loop with a Halving Step

def count_halvings(n):
    steps = 0
    while n > 1:
        n = n // 2               # the range shrinks by half each iteration
        steps += 1
    return steps

Analysis: Each iteration cuts n in half rather than stepping through it linearly — this is the defining signature of O(log n) from Chapter 2. Space: one counter variable → O(1).

4. Worked Example 3: A Hidden Nested Loop

def has_common_element(list_a, list_b):
    for a in list_a:                # O(n)
        if a in list_b:              # `in` on a list is itself O(m) — HIDDEN LOOP
            return True
    return False

Analysis: It looks like a single loop, but in on a list performs its own linear scan. With list_a of size n and list_b of size m, this is O(n × m) — effectively quadratic if the lists are similar in size. This is exactly the "function call inside a loop" trap from Chapter 3 — converting list_b to a set first (Module 8) would drop this to O(n + m).

5. Worked Example 4: Recursion

def sum_list(items):
    if not items:
        return 0
    return items[0] + sum_list(items[1:])     # note: items[1:] COPIES the list

Analysis: This makes n recursive calls → O(n) time, seemingly. But items[1:] creates a new list copy at every call, and that copy itself takes O(k) time/space where k is the remaining length. Summed across all calls, that's O(n) + O(n-1) + ... + O(1) = O(n²) time, and the recursion stack itself adds O(n) space on top of the copies. This is a classic hidden-cost trap — the fix is to pass an index instead of slicing:

def sum_list_fixed(items, index=0):
    if index == len(items):
        return 0
    return items[index] + sum_list_fixed(items, index + 1)
    # No copying — O(n) time, O(n) space (call stack only)

6. Common Traps to Watch For

• Slicing inside recursion or loops (items[1:], items[:k]) silently costs O(k) per slice — it's not free.
• in on a list is O(n), not O(1) — only in on a set or dict is O(1) average case (Module 8).
• String concatenation in a loop (result += char) can be O(n²) overall in some languages/implementations, since each += may create a new string — prefer building a list and ''.join() at the end.
• Sorting inside a loop — calling .sort() (O(n log n)) inside an O(n) loop makes the whole function O(n² log n), easy to miss at a glance.

7. Try It Yourself

Before continuing to Module 2, determine the time and space complexity of each:

# (a)
def mystery_a(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i, j, k)
 
# (b)
def mystery_b(items):
    return items[0] + items[-1]
 
# (c)
def mystery_c(items, target):
    seen = set()
    for item in items:
        if target - item in seen:
            return True
        seen.add(item)
    return False

8. Summary & Next Steps

Key Takeaways

• Analyzing complexity is mechanical: identify loops/recursion, check for hidden costs (slicing, in on lists, sorting), then apply the add/multiply rules.
• Slicing, list-membership checks, and sorting are the most common sources of hidden complexity that make code look better than it actually performs.
• This checklist will be applied to every algorithm from here forward — it's worth returning to if a later module's complexity claim (e.g., "this is O(n)") isn't obvious to you.

Concept Check

1. Why does items[1:] inside a recursive call change the overall time complexity from O(n) to O(n²)?
2. Why is target - item in seen in Example (c) O(1) on average, but target - item in items would not be?
3. Walk through Example (a) and confirm why it's O(n³), not O(n²).

Next Module

→ Module 2: Arrays & Strings

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index