CS136 Study Guide - Insertion Sort, Sorting Algorithm
Document Summary
Solution: in the best case, a starts in sorted order so that the while loop never runs. Since there are n loop iterations, the total cost is (n) operations. In the worst case, a starts in reverse sorted order, so every newly encountered item is the smallest yet seen. Thus the while loop will run until j = 1, or (i) iterations of cost (1). The statement if x then y costs (cost x) if x is false and (cost x + cost y ) if x is true. Alternatively, cost is o(cost x + cost y ) and (cost x), but these bounds may be too crude for some analyses. Similarly, heapremove costs o(log n), but in certain cases this bound can be too crude, e. g. , if all heap keys are equal then heapremove costs (1). Solution: asymptotically the 2n will cause f (n) to grow fastest.
