The Engineer's Bible | Volume 1: Foundations

Chapter 13: Measuring Efficiency (Algorithms & Big O)

Learning Objectives

Prerequisites

Chapter 4: Loops. Chapter 6: Arrays. Chapter 7: Hash Maps.

Why Does This Exist?

A junior engineer writes a sorting script for 10 users. It runs instantly. They deploy it.

A year later, the company has 100,000 users. The exact same script suddenly takes 3 hours to run. The server crashes. The company loses money.

Why did it work for 10 but fail for 100,000? Because the relationship between the input size and the execution time was exponential, not linear.

We needed a mathematical language to predict how an algorithm behaves as the data scales to infinity. We needed Big O Notation.

History

In the 1960s, computers were incredibly slow. Every CPU cycle was precious. Mathematicians brought concepts from asymptotic analysis into computer science to mathematically prove which sorting method was definitively "better".

It proved that an efficient algorithm on a slow 1980s computer will eventually beat an inefficient algorithm running on a modern supercomputer, simply because of how the math scales.

Mental Model

Imagine finding the name "Zebra" in a physical phone book.

O(N) - Linear: You start at page 1, read every name, turn the page, and repeat until you hit Z. If the book is twice as thick, it takes twice as long. (Slow).

O(log N) - Logarithmic: You open the book exactly in the middle (M). You see M comes before Z. You rip the first half of the book off and throw it away. You open the remaining half in the middle again. You keep halving it. Even if the phone book had a billion pages, you would find "Zebra" in just 30 steps. (Extremely Fast).

Internal Working

Big O Notation ignores seconds. It counts the maximum number of operations the CPU must perform in the worst-case scenario.

Let N be the number of items (the input size).

Big O strips away constants. O(2N) is just written as O(N). We only care about the curve of the line as it approaches infinity.

Syntax

Here are code examples of the different complexities:

1# O(1) - Constant Time
2def get_first(items):
3    return items[0]
4
5# O(N) - Linear Time
6def print_all(items):
7    for item in items:
8        print(item)
9
10# O(N^2) - Quadratic Time (Danger!)
11def print_pairs(items):
12    for i in items:
13        for j in items:
14            print(i, j)

Visual Explanation

Execution Time ^ | / O(N^2) - Nested Loops | / | / | / | / | / | / O(N) - Single Loop | /----------- | / | / O(log N) - Binary Search | /----------------- | / | / O(1) - Dictionary/Array Index |------------------------- +------------------------------------> Input Size (N)

Tiny Example

Converting an O(N) algorithm to O(1) using a Hash Map.

1# BAD: O(N) - Must search the whole list
2usernames_list = ["alice", "bob", "charlie"]
3is_taken = "bob" in usernames_list
4
5# GOOD: O(1) - Instant lookup
6usernames_dict = {"alice": True, "bob": True}
7is_taken = usernames_dict.get("bob")

Common Mistakes

The Hidden O(N) Loop

1def check_duplicates(items):
2    seen = []
3    for item in items:        # O(N) loop
4        if item in seen:      # HIDDEN O(N) loop!
5            return True
6        seen.append(item)
7    return False

Why it fails: The in list operator in Python is a linear search. It scans the array. By putting it inside a for loop, you accidentally created an O(N²) algorithm without explicitly writing two loops.

The Fix: Make seen a Dictionary (or Set). The in dict operator is O(1). The whole function becomes O(N).

Debugging

How do professionals find slow code?

You can't just stare at it. You use a Profiler. In Python, the cProfile module runs your code and prints out exactly how many milliseconds the CPU spent inside every single function.

If a function took 90% of the total execution time, that is your bottleneck. Apply Big O analysis there.

Mini Project

Time: 20 minutes.

Goal: Prove the math.

Write an O(N²) nested loop that counts up to 1000 * 1000. Use Python's time module to record the start time and end time. Print the difference. Now, change the inputs to 5000 * 5000. Notice how the time doesn't increase by 5x, it increases by 25x!

Bigger Project

Time: 1.5 hours.

Goal: Implement Binary Search.

Take an already sorted array of 100 numbers. Write a while loop. Track a low index and a high index. Calculate the mid index. If the middle number is your target, return it. If the middle number is too low, move your low index to mid + 1. If too high, move your high index to mid - 1. This is O(log N). Print how many loop cycles it took (it should never take more than 7!).

Production Usage

Google Search processes billions of pages in a fraction of a second.

They do not use O(N) to scan the internet every time you search. They spend days pre-building an inverted index (a massive Hash Map). When you hit enter, your search is largely an O(1) lookup into that pre-built index.

Best Practices

Interview Questions

Easy: What does O(1) mean?

Answer: Constant time. The operation takes the exact same amount of time regardless of how much data exists.

Medium: Why is a nested loop usually O(N²)?

Answer: Because for every 1 iteration of the outer loop, the inner loop must execute N times. N * N = N².

Hard: What is the time complexity of sorting an array?

Answer: The absolute best general-purpose sorting algorithms (like Merge Sort or Timsort) run in O(N log N) time. You cannot generally sort faster than this because you must at least look at every element, and comparing them takes logarithmic time.

Revision Sheet

I now understand WHY this exists.

Connections