4. Complexity [15 marks] For each of the following operations, algorithms, or tasks, give the most...

 

Transcribed Image Text:

4. Complexity [15 marks] For each of the following operations, algorithms, or tasks, give the most precise or informative expression you can, using the asymptotic notation we have used in class (0,2,0), for the worst-case time. For full marks, you must briefly but clearly justify each answer. (a) [3 marks] Inserting a new item into a heap of size n. (b) [3 marks] Deleting an element from an AVL Tree of size n. (c) [3 marks] Sorting an n-element array using Insertion Sort. (d) [3 marks] Inserting n elements into an B-Tree, and then removing half of them one-by-one. (e) [3 marks] Suppose we are given n elements and want to find the 100 smallest (assume n is larger than 100). We can do it this: Insert all n elements into an AVL tree T, then do an in-order traversal of T, but stop after visiting 100 nodes. How much time will it take? Why? 4. Complexity [15 marks] For each of the following operations, algorithms, or tasks, give the most precise or informative expression you can, using the asymptotic notation we have used in class (0,2,0), for the worst-case time. For full marks, you must briefly but clearly justify each answer. (a) [3 marks] Inserting a new item into a heap of size n. (b) [3 marks] Deleting an element from an AVL Tree of size n. (c) [3 marks] Sorting an n-element array using Insertion Sort. (d) [3 marks] Inserting n elements into an B-Tree, and then removing half of them one-by-one. (e) [3 marks] Suppose we are given n elements and want to find the 100 smallest (assume n is larger than 100). We can do it this: Insert all n elements into an AVL tree T, then do an in-order traversal of T, but stop after visiting 100 nodes. How much time will it take? Why?