(Solved): 8. Suppose the Insertion Sort algorithm for sorting an array has been modified: instead of sequentia ...

8. Suppose the Insertion Sort algorithm for sorting an array has been modified: instead of sequential search, binary search is used to find the position for inserting the next element into the already sorted initial segment of the list.

8. Suppose the Insertion Sort algorithm for sorting an array has been modified: instead of sequential search, binary search is used to find the position for inserting the next element into the already sorted initial segment of the list. 8a. What is the AVERAGE case big-O for the number of **comparisons \( * \star \) (in 1 point terms of the length of the array \( \mathrm{n} \) )? \( O(1) \) \( O(n) \) \( O\left(n^{\wedge} 2\right) \) \( O\left(2^{\wedge} n\right) \) \( \mathrm{O}(\log n) \) \( o(n \log n) \) 8b. What is the WORST case big-0 for the number of \( { }^{\star *} \) comparisons \( ^{\star \star} \) (in 1 point terms of the length of the array \( n \) )? \( \mathrm{O}(1) \) \( O(n) \) \( O\left(n^{\wedge} 2\right) \) \( O\left(2^{\wedge} n\right) \) \( O(\log n) \) \( o(n \log n) \) 8c. What is the BEST case big-0 for the number of \( { }^{\star \star} \) comparisons \( ^{\star \star} \) (in terms 1 point of the length of the array \( n \) )? \( O(1) \) \( O(n) \) \( O\left(n^{\wedge} 2\right) \) \( O\left(2^{\wedge} n\right) \) \( O(\log n) \) \( o(n \log n) \)