Algorithm Analysis

Algorithm analysis answers the question the previous topic kept raising but never measured: given two algorithms that both solve the same problem, which one actually costs less, and how does that cost grow as the input gets bigger? Big O notation describes that growth using the input size n, deliberately ignoring constant factors and lower-order terms because what matters at scale is the shape of the curve, not the exact number of operations on any one machine: binary search from the previous topic is O(log n) because each comparison discards half the remaining range, linear search is O(n) because it may have to check every element, bubble sort is O(n squared) because it compares roughly every pair, and merge sort is O(n log n) because its recursive halving does log n levels of work, each level touching all n elements once during the merge. A constant-time operation, O(1), costs the same regardless of input size, which is exactly why an array's indexed access from the data-structures topic is the gold standard for speed, and why a hash table's average-case lookup is prized even though its worst case degrades under heavy collisions. Space complexity applies the identical idea to memory instead of time: bubble sort rearranges elements in place and needs essentially no extra memory beyond the input itself, an O(1) space cost, while merge sort's recursive splitting-and-merging approach, as built in the previous topic's worked example, allocates a second array to merge into, an O(n) space cost — so merge sort trades memory for speed, a tradeoff that recurs constantly across computing and is never free. Correctness is a separate question from both: an algorithm can be fast and still be wrong, which is exactly why the debugging-and-testing topic's assertions and test cases exist as the tool for checking it, and a formal correctness argument typically proves two things about a loop or recursive step — that it makes genuine progress toward the base case every time, and that whatever invariant it depends on (like "the left half is fully sorted before the merge step begins") actually holds at every step, not just the first one. None of this analysis is about benchmarking one specific run on one specific machine; it is about understanding, in general, how a design choice behaves as the problem gets larger, which is precisely the lens the next topic, programming paradigms, will apply to an entirely different kind of design choice: not which algorithm, but which overall style of structuring code.