Algorithm Complexity: Big O Notation

Imagine two friends, Aarav and Diya, are each given a printed telephone directory for all of Bengaluru — millions of names, sorted alphabetically. You ask both of them to find the phone number of "Sharma, Rahul." Aarav starts at page one and reads every single name, top to bottom, until he reaches Rahul. Diya opens the book right in the middle, sees she has gone too far or not far enough, throws away half the book, opens the middle of what remains, and keeps halving. Aarav might read a million names. Diya finds Rahul after checking only about twenty. Both of them are "searching." Both will eventually give you the right number. So why does one finish before the chai gets cold while the other is still turning pages an hour later?

That question — how does the work an algorithm does grow as the input gets bigger? — is the entire subject of this chapter. The tool computer scientists use to answer it is called Big O notation. It lets us compare Aarav's method and Diya's method without ever running them on a computer, without caring whether the computer is a fast gaming laptop or a cheap Raspberry Pi, and without getting distracted by tiny details. By the end, you will be able to look at a piece of code and say, honestly and correctly, "this one will still be fast when the input is a million items, and that one will crawl."

Counting steps, not seconds

Your first instinct might be to measure speed with a stopwatch: run the program, time it, done. But this is a trap. If Diya's laptop is twice as fast as Aarav's, timing would make her method look good even if she used Aarav's slow strategy. Speed-in-seconds mixes up two different things: how good the algorithm is and how fast the machine is. We only want to measure the algorithm.

So instead of counting seconds, we count basic steps — how many times the algorithm does its main unit of work. For searching, the natural unit of work is "compare one name to the target." We then ask: if the list has n items, how many comparisons do we make? The letter n always stands for the size of the input. Getting into the habit of describing everything as a function of n is the single most important move in this whole chapter.

Let us count Aarav's method, which has a proper name: linear search. Here it is in Python, searching a list for a target value:

def linear_search(items, target):
    for i in range(len(items)):      # look at each item, one by one
        if items[i] == target:       # compare it to what we want
            return i                 # found it -- give back the position
    return -1                        # never found it

names = ["Aarav", "Diya", "Farhan", "Ishaan", "Meera", "Priya", "Rahul", "Zoya"]
print(linear_search(names, "Rahul"))   # prints 6
print(linear_search(names, "Kabir"))   # prints -1

Trace it. The list has 8 names, so n = 8. Searching for "Rahul", the loop compares "Aarav", "Diya", "Farhan", "Ishaan", "Meera", "Priya", "Rahul" — that is 7 comparisons before it returns the index 6 (positions start at 0, so Rahul is at index 6). Searching for "Kabir", which is not in the list, the loop compares all 8 names, finds nothing, and returns -1. That second case is the worst case: the target is absent, so we are forced to check every element. In the worst case, a list of size n costs exactly n comparisons.

Why we care about the worst case

You might protest: "But if I'm lucky, the item is first and I do only one comparison!" True. That is the best case. But best cases are unreliable — you cannot promise a user that their data will be lucky. When engineers at IRCTC or UPI design a system, they must guarantee it stays fast even on the hardest input, because the hardest input will show up during a Tatkal booking rush. So Big O almost always describes the worst case: the promise "no matter how bad the input, it will not be slower than this." Linear search, worst case, is proportional to n. We write this as O(n), read aloud as "big-oh of n" or "order n."

Diya's method: binary search and the power of halving

Diya's method only works because the directory is sorted. Because it is sorted, one comparison tells her not just "is this the name?" but also "is my target earlier or later than here?" — which lets her throw away half the remaining names in a single step. This is binary search:

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    steps = 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2      # the middle position
        if items[mid] == target:
            return steps             # found it -- return how many steps it took
        elif items[mid] < target:
            low = mid + 1            # target is in the right half
        else:
            high = mid - 1          # target is in the left half
    return steps

nums = [1, 2, 3, 4, 5, 6, 7, 8]
print(binary_search(nums, 7))        # prints 3

Let us trace the search for 7 in [1,2,3,4,5,6,7,8] (n = 8) slowly, because the counting here is the heart of the chapter. Start with low=0, high=7.

• Step 1: mid = (0+7)//2 = 3, so items[3] = 4. Since 4 < 7, the target is to the right; set low = 4. Half the list is gone.
• Step 2: mid = (4+7)//2 = 5, so items[5] = 6. Since 6 < 7, set low = 6.
• Step 3: mid = (6+7)//2 = 6, so items[6] = 7. Found it! Return 3.

Three steps to search eight items. Linear search would have taken up to eight. That gap does not sound dramatic yet — but watch what happens as n grows, because binary search cuts the problem in half every step. Starting from n items, how many times can you halve before only one is left? That count is the logarithm base 2 of n, written log₂(n).

You do not need to be scared of logarithms. Here log₂(n) simply means "how many times you halve n to reach 1," which is the same as "2 raised to what power gives n." Since 2×2×2 = 8 = 2³, we have log₂(8) = 3 — exactly the three steps we counted. Here is the table that should genuinely surprise you:

       n            linear search (O(n))     binary search (O(log n))
       8                     8                         3
     1,000                 1,000                       10
 1,000,000             1,000,000                       20
 1,000,000,000     1,000,000,000                       30

Read the bottom row again. To search a billion sorted items, binary search needs about 30 comparisons. This is why Diya wins so overwhelmingly on the full Bengaluru directory: doubling the size of the data adds just one extra step to binary search, while it doubles the work for linear search. We call binary search O(log n), and log n is one of the most desirable complexities an algorithm can have.

The picture: how the curves grow

Numbers in a table are convincing, but seeing the shapes side by side is what makes the idea stick. The diagram below plots the amount of work (vertical) against the input size n (horizontal) for the four complexity classes you meet most often. Notice how they fan apart: what starts as a small gap becomes an unbridgeable gulf.

The order from best to worst, as n grows large, is: O(1) (constant — does not grow at all), then O(log n), then O(n), then O(n²) and worse. Memorise this ranking; it is the vocabulary you will use for the rest of your life in computing.

O(1): work that does not care how big n is

The flat blue line is constant time, O(1). Some operations take the same amount of work no matter how large the data is. Looking up marks[3] in a Python list, or checking whether a dictionary contains a key, does not get slower when the list or dictionary grows:

def first_element(items):
    return items[0]      # one step, always -- whether items has 5 or 5 million entries

Whether items holds five numbers or five million, grabbing the first one is a single step. That is the dream: O(1). When you check a student's roll number in a well-built database and the answer comes back instantly regardless of how many students are enrolled, you are feeling O(1) in action.

O(n²): the cost of nesting a loop inside a loop

The steep red curve, O(n²), usually appears when you loop over your data inside another loop over the same data. Suppose you want to check whether a list of exam scores contains any duplicate:

def has_duplicate(scores):
    n = len(scores)
    for i in range(n):               # outer loop runs n times
        for j in range(i + 1, n):    # inner loop, for each i
            if scores[i] == scores[j]:
                return True
    return False

print(has_duplicate([88, 91, 74, 91, 60]))   # prints True  (91 appears twice)
print(has_duplicate([88, 91, 74, 60]))        # prints False

For each of the n items, the inner loop compares it against the items after it. The total number of comparisons is 1 + 2 + 3 + ... which for a list of size n works out to n(n−1)/2 pairs. For n = 5 that is (5×4)/2 = 10 comparisons. The exact formula has a ½ and an n in it, but the fastest-growing piece is the n² term, and that is what dominates when n is large. So we call it O(n²). For n = 1,000 this is about half a million comparisons; for n = 100,000 it is around five billion. A doubling of the input quadruples the work. This is why an O(n²) algorithm that feels instant on your 20-item test list can freeze completely on real data.

The big idea: keep only the fastest-growing term, drop the constants

Here is the rule that makes Big O simple to use, and it is exactly where students get confused, so read slowly. Big O deliberately throws away two things: constant multipliers, and slower-growing terms. If you carefully count an algorithm and get, say, 3n² + 500n + 200 steps, its Big O is simply O(n²). We drop the 3, we drop the 500n, we drop the 200.

Why is this allowed? Because Big O describes behaviour as n gets large, and for large n the n² term utterly swamps everything else. Try n = 1,000: the n² term is 3,000,000 while the 500n term is only 500,000 and the +200 is a rounding error. As n keeps growing, the n² share of the total climbs toward 100%. The constants and smaller terms depend on fiddly details — how fast one particular machine is, how the code is written — and Big O is designed to ignore exactly those details so we can talk about the algorithm's quality, not the machine's.

The misconception that trips up almost everyone

Here is the single most common mistake students make with Big O: believing that a lower Big O always means a faster program on your actual input. It does not. Big O tells you about the trend as n grows toward infinity, not about small inputs.

Concretely: suppose algorithm A takes 100n steps (that is O(n)) and algorithm B takes n² steps (that is O(n²)). Big O says A is the "better" algorithm. But for n = 50, algorithm A does 100 × 50 = 5,000 steps while algorithm B does 50 × 50 = 2,500 steps — B is actually twice as fast here! The crossover happens at n = 100 (both do 10,000 steps); only for n above 100 does the O(n) algorithm pull ahead, and then it pulls ahead forever. So the correct reading of Big O is: "for large enough inputs, the lower Big O wins — and it wins by an ever-widening margin." For tiny inputs, the hidden constants can flip the result. This is why real libraries sometimes use a "worse" O(n²) sorting method for very short lists and switch to a better one only when the list is long. Never say "O(n) is always faster than O(n²)." Say "O(n) scales better."

A worked exam-style example

Let us put it all together on one function and reason like an examiner would. What is the Big O of this?

def summarise(marks):          # marks is a list of length n
    total = 0
    for m in marks:            # loop A: runs n times
        total = total + m
    average = total / len(marks)

    above = 0
    for m in marks:            # loop B: runs n times
        if m > average:
            above = above + 1

    return total, average, above

Step through it. The first loop runs n times. The average line is a single O(1) operation. The second loop runs n times. The two loops are one after another, not nested, so we add their costs: n + 1 + n = 2n + 1 steps. Drop the constant multiplier and the +1, and the answer is O(n). The key insight to state in an exam: sequential loops add (n + n = 2n → O(n)), but nested loops multiply (n × n = n² → O(n²)). That one distinction answers a large fraction of complexity questions you will ever be asked.

Practice: your turn to do the work

Do not just read these — actually work them out on paper, then check your reasoning against the summary that follows.

1. Trace it. Using the binary_search function above on the list [1,2,3,4,5,6,7,8], hand-trace the search for the value 3. Write down low, high, and mid at each step. How many steps does it take? (Answer: low/high start 0/7 → mid 3 (value 4, too big) → high 2 → mid 1 (value 2, too small) → low 2 → mid 2 (value 3, found). Three steps.)
2. Classify each. Give the Big O of: (a) printing every item in a list once; (b) printing every possible pair of items using two nested loops; (c) checking if the number at index 0 is even; (d) binary search on a sorted array. (Answers: a → O(n); b → O(n²); c → O(1); d → O(log n).)
3. Simplify. An algorithm is measured to take exactly 5n² + 20n + 100 steps. What is its Big O, and roughly how many steps for n = 1,000? (Answer: O(n²); at n=1,000 that is 5,000,000 + 20,000 + 100 = 5,020,100 steps, dominated by the 5,000,000 from the n² term.)
4. Think carefully. Algorithm P takes 10n steps; algorithm Q takes n² steps. For what value of n do they do the same amount of work, and for which one is Q faster? (Answer: 10n = n² when n = 10; for n below 10, Q does fewer steps and is faster; for n above 10, P wins and keeps winning.)
5. Design question. You must repeatedly look up students by roll number in a list of 10 million records, thousands of times per second during results day. Would you keep the list unsorted and use linear search (O(n)), sort it once and use binary search (O(log n)), or something else? Justify using the growth table. (Answer: linear search would cost up to 10 million comparisons per lookup; binary search costs about 24 — since log₂(10,000,000) ≈ 23.3 — after a one-time sort, so binary search is overwhelmingly better for many repeated lookups.)

Summary: what you now know

Big O notation is how computer scientists describe the way an algorithm's work grows as its input size n grows — the property that decides whether your program stays fast at scale or collapses. Instead of timing seconds (which mixes up the algorithm with the machine), we count basic steps as a function of n, and we focus on the worst case because that is the promise we can actually guarantee. We keep only the fastest-growing term and drop constant factors, because those small details are exactly what we want to ignore when comparing algorithms.

You met the core family, ranked from best to worst for large n: O(1) constant (a direct index lookup), O(log n) logarithmic (binary search — halving, about 30 steps for a billion items), O(n) linear (a single loop over the data), and O(n²) quadratic (nested loops over the same data). You learned the rule that sequential loops add while nested loops multiply, and — most importantly — you learned the honest limit of Big O: it describes the trend for large inputs, not a guarantee that the lower Big O is faster on every small input. When Aarav read a million names and Diya found Rahul in twenty, you were watching O(n) lose to O(log n). Now you can predict that outcome before either of them turns a single page — which is exactly the superpower Big O gives you.