Complexity analysis answers a practical question: as the input grows, how fast does the running time grow? Big-O notation describes the upper bound: O(1) means constant time regardless of input size, O(log n) means time grows with the number of halvings, O(n) grows linearly, O(n log n) is the sorting benchmark, and O(n²) grows with the square of the input. The analysis counts the dominant operation and drops constants and lower-order terms, because for large inputs the fastest-growing term decides.
Searching shows why this matters. Linear search checks elements one by one: O(n) worst case, but it works on any array. Binary search repeatedly halves a sorted array: O(log n), but it requires sorted input. A common exam trap is applying binary search to an unsorted array: the halving logic assumes order, so on unsorted data it can miss an element that is present.
Worked example — merge sort on 8 elements. Merge sort splits the array in half, sorts each half recursively, and merges the sorted halves. Its recurrence is T(n) = 2T(n/2) + n, which solves to O(n log n) in all cases: best, average and worst. For n = 8, the worst-case comparison count is n log2 n − n + 1 = 8 × 3 − 8 + 1 = 17 comparisons. That stability and guaranteed O(n log n) time are why merge sort is the safe choice when worst-case behaviour matters, at the cost of O(n) extra space.