Count Operations

Problem

Given the following function, determine its time complexity and explain your reasoning.

def mystery(n):
    total = 0
    for i in range(n):           # loop A
        for j in range(n):       # loop B
            total += 1
    for k in range(n):           # loop C
        total += k
    return total

What is the Big-O complexity? What would change if loop B ran range(i) instead of range(n)?

Approach

Break it down loop by loop and then combine.

• Loop A × Loop B: nested loops both running n times → O(n²)
• Loop C: single loop running n times → O(n)
• Total: O(n²) + O(n) → dominant term is O(n²)

For the variant where loop B runs range(i):

• Outer i goes 0 → n-1, inner j goes 0 → i
• Total iterations = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2
• Still O(n²) — same class, different constant