C++ DATA STRUCTURES

9. Show your reasoning, use human-oriented units such as hours, months, o:r years rather than enormous numbers of seconds. State any assumptions that you make in answering these questions Using the O() notation, and N to represent the number of data items involved, what is the speed of i. Insertion sort ii. Merge sort iii. Bubble sort iv. Binary Chop Search v. Searching a Linked List vi. Searching a well balanced Bi inary Tree If an implementation of Insertion Sort on a particular computer is found to take 1,000 seconds to sort 1,000,000 items i. How long would you expect it to take to sort 3,000,000 items? ii. How long would you expect it to take to sort 1,000 items? iii. How long would you expect it to take to sort 1,000,000 items? iv. How long would you expect it to take to sort 1,000,000,000 items? C. If it takes one tenth of a second to search a linked list of 1,000,000 items, and those items were then put into a binary tree, how long would you expect a search of that tree to take? If it takes Bubble Sort an hour to sort an array of 1,000,000 items i. How long would it take for a Binary Chop Search to find an item in the resulting sorted array? ii. How long would it have taken to sort the array if Merge Sort had been used instead of Bubble Sort? You may not have heard of "Boolean Satisfiability", but its speed is O(2") That is, Exponential If it takes Boolean Satisfiability 1mS for 10 items, how long would it take for 100 items