Part of the motivation for asymptotic analysis was that algorithms are typically analyzed ignoring constant factors. Ignoring constant factors in analyzing an algorithm may seem strange: if algorithm...

Part of the motivation for asymptotic analysis was that algorithms are typically analyzed ignoring constant factors. Ignoring constant factors in analyzing an algorithm may seem strange: if algorithm A runs twice as fast as B, then A is way faster! But the reason we care more about asymptotic running time is that even an improvement by a factor of 2 is quickly swamped by an asymptotic improvement for even slightly larger inputs. Here are a few examples

Suppose that linear search can find an element in a sorted list of n elements in n steps on a particular machine. Binary search (perhaps not implemented especially efficiently) requires 100 log n steps. For what values of n ≥ 2 is linear search faster? Alice implements Merge Sort so, on a particul