Big-O is about growth, not speed
Big-O does not tell you how many seconds your code takes. It tells you how the cost grows when the input grows. That is the durable question, because hardware gets faster every year but n² stays n².
This is why constants get dropped. An algorithm doing 3n + 200 steps is written O(n): as n heads for a million, the 3 and the 200 stop mattering, and the shape of the curve is all that survives.
Push n to 120 and switch the y-axis to log. The gap between O(n log n) and O(n²) is what separates a sort that finishes and a sort that hangs.
The numbers that make it real
At n = 1,000,000, assuming a billion operations per second:
| Complexity | Operations | Rough time |
|---|---|---|
| O(log n) | 20 | instant |
| O(n) | 1,000,000 | 1 millisecond |
| O(n log n) | 20,000,000 | 20 milliseconds |
| O(n²) | 10¹² | ~17 minutes |
| O(2ⁿ) | 10³⁰¹⁰³⁰ | longer than the universe has existed |
This is why the choice matters
Between O(n log n) and O(n²) there is no clever optimisation, no faster laptop, and no compiler flag that closes the gap. At scale you must change the algorithm.
Sorting, watched step by step
Bubble sort repeatedly swaps neighbours that are out of order. Simple, and O(n²) — genuinely useless beyond teaching.
Insertion sort builds a sorted region on the left, sliding each new element back into place. Also O(n²), but it is O(n) on nearly-sorted data, which makes it excellent for small or almost-ordered inputs.
Selection sort finds the minimum and swaps it into place. Always O(n²) comparisons, but only n−1 swaps — useful when writing is expensive.
Quicksort picks a pivot, partitions everything around it, and recurses. O(n log n) on average and the fastest in practice, though a bad pivot on already-sorted data degrades it to O(n²).
Run Bubble, then Quick on the same shuffle. Compare the comparison counters at the end — that number is Big-O made concrete.
Binary search: the log in O(log n)
Searching a sorted array by halving is the cleanest O(log n) there is. Check the middle. Too big? Throw away the top half. Too small? Throw away the bottom. Each step deletes half the remaining possibilities.
Starting from a million items: 500,000 → 250,000 → 125,000 → … → 1. Twenty steps. Doubling the data adds exactly one step, which is what logarithmic growth means.
What makes something an algorithm
Before analysing efficiency, be precise about what is being analysed. An algorithm is a finite sequence of unambiguous steps that takes defined inputs and produces defined outputs. All four conditions are examinable.
Finite — it must terminate. Unambiguous — every step has exactly one interpretation. Defined inputs and outputs — you know what it needs and what it produces. Effective — every step is something that can actually be carried out.
| Written as | Strength | Weakness |
|---|---|---|
| Flowchart | the flow of control is visible at a glance | unwieldy beyond about twenty steps |
| Pseudocode | close to real code, scales to long algorithms | no visual sense of the structure |
| Structured English | readable by a non-programmer | easy to leave ambiguous |
| Actual code | unambiguous and runnable | ties the idea to one language |
Correctness and efficiency are separate questions
An algorithm can be correct and unusably slow, or fast and wrong. Establish correctness first — trace it by hand on a small input and check the answer — and only then ask about efficiency. Optimising an algorithm that produces the wrong answer is the most reliable way to waste an afternoon.
Searching: linear against binary
A linear search examines each item in turn until it finds the target or runs out. It works on any list in any order, and on average examines half of it — O(n).
A binary search requires the list to be sorted. It looks at the middle item, and since the list is ordered it can discard half the remaining items at every step — O(log n). For a million items, linear search averages 500 000 comparisons and binary search needs at most 20.
The catch is the precondition. Sorting an unsorted list to permit one binary search costs more than simply searching it linearly. Binary search pays off when the same list is searched many times.
A list of 1000 sorted names is searched. How many comparisons does binary search need in the worst case, and why?
- Each comparison discards half of the remaining items.The list is sorted, so knowing the target is smaller than the middle item rules out the entire upper half at once.
- After each step the remaining size is 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1.Halving repeatedly, rounding up.
- That is 10 steps, and
2¹⁰ = 1024, just over 1000.The worst case is the smallest power of 2 that reaches the list size. - So at most 10 comparisons, against an average of 500 for a linear search.Doubling the list to 2000 adds one comparison, not a thousand — which is what O(log n) means in practice.
10 comparisons, because 2¹⁰ = 1024 ≥ 1000.
Comparing two algorithms fairly
Timing a program with a stopwatch measures the machine, the language and the compiler as much as the algorithm. A fast computer running a poor algorithm beats a slow computer running a good one — right up to the point where the input grows, and then it does not.
So algorithms are compared by counting the operations they perform as a function of the input size n, and reporting only how that count grows. Constants and lower-order terms are dropped, because for large n they stop mattering: 3n² + 50n + 900 is O(n²), since the n² term eventually dominates everything else however large the other numbers look.
| Case | Means | Example: linear search |
|---|---|---|
| Best case | the most favourable input | target is the first item — 1 comparison |
| Average case | typical input | target is halfway — n/2 comparisons |
| Worst case | the least favourable input | target is last or absent — n comparisons |
| Space complexity | extra memory needed | O(1) — no extra storage per item |
Why the worst case is usually the one quoted
An average depends on assumptions about the input that may not hold, and a best case tells you almost nothing. The worst case is a guarantee: whatever the input, it will not be slower than this. For anything that must respond within a time limit, a guarantee is the only figure worth having — which is why O-notation normally describes the worst case unless the question says otherwise.