Big-O Notation: Expressing Performance with Numbers

After completing this topic, you will be able to:

• Understand what Big-O notation is.
• Estimate the time complexity of code.
• Explain the differences between O(1), O(n), O(n²), and O(log n).

Why do we need Big-O?

"This code is slow." — We need to be able to say how slow it is and how much slower it will become as the data increases. Big-O is a notation that expresses how the number of operations increases as the input size (n) increases.

It doesn't measure execution time in seconds. Seconds vary depending on computer performance. Big-O talks about growth patterns.

O(1) — Constant Time

It always takes the same amount of time, regardless of the input size.

def get_first(items):
    return items[0]  # Takes 1 operation, whether it's 100 or 1 million items.

# Dictionary lookups are also O(1)
user = {"name": "Kim Hoon"}
user["name"]  # Hash calculation → immediate access

If the data increases by 10 times, the time remains the same.

O(n) — Linear Time

The time increases proportionally to the input size.

def find_max(items):
    max_val = items[0]
    for item in items:      # Iterates n times
        if item > max_val:
            max_val = item
    return max_val

If the list has 100 items, it compares 100 times; if it has 1 million, it compares 1 million times. If the data increases by 10 times, the time also increases by 10 times. Usually, if there's a single for loop that iterates through everything, it's O(n).

O(n²) — Quadratic Time

Nested loops are a typical example.

def has_duplicate(items):
    for i in range(len(items)):         # n times
        for j in range(i + 1, len(items)):  # Up to n times
            if items[i] == items[j]:
                return True
    return False

If there are 100 items, it performs approximately 5,000 operations; if there are 1,000, it performs approximately 500,000; if there are 10,000, it performs approximately 50,000,000. If the data increases by 10 times, the time increases by 100 times. This is why O(n²) is dangerous.

# Improved to O(n) using a set
def has_duplicate_fast(items):
    seen = set()
    for item in items:       # n times
        if item in seen:     # Set lookup is O(1)
            return True
        seen.add(item)
    return False

Solving the same problem in O(n) reduces the 50,000,000 operations to 10,000 for 10,000 items.

O(log n) — Logarithmic Time

At each step, the search range is reduced by half. Binary search is a typical example.

def binary_search(sorted_list, target):
    low, high = 0, len(sorted_list) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1        # Discard the left half
        else:
            high = mid - 1       # Discard the right half
    
    return -1  # Not found

With 1 million items, it finds the item with a maximum of 20 comparisons (log₂(1,000,000) ≈ 20). O(n) would take 1 million, while O(log n) takes 20. However, it only works on sorted data.

Comparison at a Glance

O(n²) becomes impractical when n exceeds 10,000. O(n log n) is the complexity of efficient sorting algorithms (merge sort, quick sort).

Key Rules for Reading Big-O

1. Constants are dropped: O(3n) = O(n), O(100) = O(1)
2. Lower order terms are dropped: O(n² + n) = O(n²) — When n is large, n² dominates n
3. Consider the worst-case scenario: When searching a list, it might be O(1) if it's found in the first position, but Big-O considers the worst-case scenario, which is O(n).

With these 3 rules, you can estimate Big-O for most code.

Key Takeaways

Big-O is a tool to determine whether "this code will survive if the data increases by 10 times." More than perfect calculation, recognizing the pattern is important — 1 for loop is O(n), nested for loops are O(n²), and halving at each step is O(log n). It's a topic that is often asked in interviews, but more importantly, it can be directly used in practice to find out "why is this API slow when there is a lot of data."