Algorithm Analysis

Algorithm analysis answers the question the previous topic kept raising but never actually measured: given two algorithms that solve the same problem, which one really costs less, and how does that cost grow as the input gets bigger? Big O notation describes that growth using the input size, deliberately ignoring constant factors because what matters at scale is the shape of the curve rather than the exact number of steps 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 every element once during the merge. Space complexity applies that same 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 allocates a second array to merge into, an O(n) space cost — and recursion itself has its own hidden space cost, since each recursive call adds a frame to the call stack covered earlier in this series, so a recursive binary search uses roughly log n stack frames at once, proportional to how many times the range gets halved, which is small but not free. Correctness is a separate question from both speed and memory: an algorithm can be fast and use little memory and still be wrong, which is exactly why the earlier topic on debugging and testing exists, and a rigorous correctness argument — closer to the kind of proof covered in discrete mathematics than to a handful of passing test cases — typically shows two things about a loop or recursive step: that it makes genuine progress toward its base case every single time, and that whatever invariant it depends on, like "the left half is already sorted before the merge step begins," actually holds at every step, not just the first one. None of this analysis is about timing one specific run on one specific machine; it is about understanding, in general, how an algorithm's cost behaves as the problem grows, which is precisely the discipline the next topic, programming paradigms, applies to an entirely different kind of design choice — not which algorithm to use, but which overall style of structuring an entire program.