Name: ___________________________________________________________________
1-3. Show, step by step, how the following algorithms will sort the list consisting of elements 11, 20, 201, and 0:
4-7. Show, step by step, how the following algorithms will sort the list consisting of elements 11, 20, 201, and 0:
8. Show, step by step, how binary search will look for an element 18 in the sorted list 0, 11, 20, and 201. No code is needed. What is the worst-case and average complexity of binary search?
9-10. Show, step by step, what will happen if we add elements 11, 20, 201, and 0 (in this order) to an (initially empty) binary search tree (no need to balance), print the elements of this tree in pre-, in-, and post-order, and then delete element 11.
11. For extra credit: prove that the worst-case complexity of a sorting algorithm cannot be smaller than O(n*log(n)).