Efficiency of algorithm in Design and analysis of algorithms free notes
Algorithms devised to solve the identical problem often vary dramatically in their efficiency. These differences can be much more significant as compared to differences due to hardware and software.
The first, known as insertion sort, takes time roughly equal to c1n2 to sort n items, where c1 is a constant that does not depend on n. That is, it takes time roughly proportional to n2. The second, merge sort, takes time roughly equal to c2n lg n, where lg n stands for log2 n and c2 is another constant that also does not depend on n.