1.Why is Insertion sort's runtime O(n) if the list is sorted? Why is Bubble sorts runtime O(n2) regardless of the sorted condition of the list? Be very specific; no generalities - I want a precise answer.
2.Specify which operations run best when the list is sorted. Then briefly describe an algorithm to implement each operation using a list organized in the optimal way.
| Task | Algorithm | Sorted/Unsorted? |
| a) Find the minimum value. | ||
| b) Find the maixmum value | ||
| c) Compute the arithmetic mean | ||
| d) Find the median (i.e., the middle value) | ||
| e) Find the mode (i.e., the value that appears the most times |
3.Assume that a virtual memory is managed using a buffer pool. The buffer pool contains five buffers and each buffer stores one block of data. Memory accesses are by disk block ID. Assume the following series of memory accesses takes place:
5 2 5 12 3 6 5 9 3 2 4 1 5 9 8 15 3 7 2 5 9 10 4 6 8 5