4) Consider the following algorithm (shown with line numbers) that finds the maximum element in an...

   

Transcribed Image Text:

4) Consider the following algorithm (shown with line numbers) that finds the maximum element in an array of positive integers. 1: int findMaxElement (int nums [], int N) { 2: int i, maxNum; maxNum = -1; for (i = 0; i < N; i++) 3: 4: 5: 6: if (nums[i] > maxNum) maxNum = nums [i]; 7: return maxNum; 8: } You can assume all elements are unique and that each occurs with equal probability. a) Best case i. ii. I Describe the best case data for this algorithm. (2 pts) Then, for this best case, state how often is line 6 executed. (2 pts) b) Worst case i. Describe the worst case data for this algorithm. (2 pts) ii. For this worst case, state how often is line 6 executed. (2 pts) 5) Suppose that for the worst case, given input size n: Algorithm 1 does f(n) = n+4n steps Algorithm 2 does f(n) = 45n+10 steps For what input sizes is algorithm 1 faster than algorithm 2, in the worst case? (4 pts) 4) Consider the following algorithm (shown with line numbers) that finds the maximum element in an array of positive integers. 1: int findMaxElement (int nums [], int N) { 2: int i, maxNum; maxNum = -1; for (i = 0; i < N; i++) 3: 4: 5: 6: if (nums[i] > maxNum) maxNum = nums [i]; 7: return maxNum; 8: } You can assume all elements are unique and that each occurs with equal probability. a) Best case i. ii. I Describe the best case data for this algorithm. (2 pts) Then, for this best case, state how often is line 6 executed. (2 pts) b) Worst case i. Describe the worst case data for this algorithm. (2 pts) ii. For this worst case, state how often is line 6 executed. (2 pts) 5) Suppose that for the worst case, given input size n: Algorithm 1 does f(n) = n+4n steps Algorithm 2 does f(n) = 45n+10 steps For what input sizes is algorithm 1 faster than algorithm 2, in the worst case? (4 pts)