1. The maximum number of comparisons with x is n. The maximum number of comparisons with index is n + 2. The maximum number of additions is n. The maximum number of assignments is n + 2.

2. The maximum number of multiplications is 2n. The maximum number of additions is n. The average number of multiplications is 2n.

3. Compute lim_{n→∞}(a_{k}n^{k} + a_{k−1}n^{k−1} + ⋯ + a_{0})/n^{k}.

4. One solution is 2^{\sqrt{n}}.

5. (k + 1)(a + kb/2).

6. 9 10 8 7 6 5 4 3 2 1; 10 8 9 7 6 5 4 3 2 1; etc.

7. Binary insertion sort with linked lists uses time O(n lg n) for key comparisons and O(n) for key assignments but still Θ(n^{2}) for other operations.

8. For one algorithm the maximum possible number of comparisons is 4 + ⌊n/4⌋ for n ≥ 4.

9. 0.5n lg n if n = 2^{k} for some k.

10. The divide-and-conquer algorithm takes time Θ(n lg^{2} n); this is better than Θ(n^{2}) for large n.

11. T (n) = 2cn(n − 1) + n if n = 2^{k} for some k.

12. T (n) = cn lg lg n + n if n = 2^{2^{k}} for some k.