Big-O in one sitting: what O(n log n) actually tells you

Big-O notation is taught as a list to memorise. It is easier as one idea: if the input gets ten times bigger, how much longer does the program take? That is all it measures.

O(1): the same time regardless of size. Looking up the first element of an array. Ten times the data, same time.

O(log n): a little longer. Binary search on a sorted list halves the problem each step, so a million items take about twenty steps, and ten million take about twenty-three. Ten times the data, three more steps.

O(n): proportionally longer. A single loop over everything. Ten times the data, ten times the time. Finding the maximum in an unsorted array is here, and there is no way to do it faster, because you have to look at every element at least once.

O(n log n): a bit worse than proportional. This is where the good sorting algorithms live: merge sort, heap sort, the average case of quicksort. Ten times the data, roughly thirteen times the time. When a question says 'sort efficiently', this is the answer they want.

O(n squared): a nested loop over the same data. Bubble sort, selection sort, comparing every pair. Ten times the data, a hundred times the time. Fine for a hundred items. Fatal for a million.

O(2 to the n): every subset. Ten times the data and the universe ends. Brute force on the travelling salesman problem.

The mistake in most exam answers is counting operations too carefully. Big-O drops constants and lower terms on purpose: 3n + 50 is O(n), and n squared + n is O(n squared). The examiner wants the shape of the growth, not the arithmetic.

The second mistake is confusing best, average and worst case. Quicksort is O(n log n) on average and O(n squared) in the worst case, and a question that says 'worst case' is checking exactly that.

If you remember one thing: find the loop that touches the most data, ask how many times it runs, and ask whether it is inside another loop. That gives the answer nine times out of ten. The full walkthrough with examples is in the Data Structures & Algorithms guide I shared.