Consider the following algorithm (shown with line numbers) that finds the maximu

Question

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) i int i, maxNum; maxNum =-1 ; for (i 0: i maxNum) maxNum = nums[i] ; return maxNum 8: You can assume all elements are unique and that each occurs with equal probability Examine how often are the instructions nums[i] maxNum on line5 an maxNun = nums [1] on line 6 are executed. a) Describe the best case data for this algorithm. Then, for the best case, state how often is line 5 executed. Then, for the best case, state how often is line 6 executed.

Explanation / Answer

a)In this following case the best case will if the array is sorted in from small to big(ascending order) so in that case the number of comparison will be 1+(n+2) and the comparison will be 1+2(n-2) if it is arranged in descending order where n denotes the number of elements.

For best case if the element is present in the first position

then

Number of times line 5 will be executed is equal to N
Number of times line 6 will be executed is equal to 1

b)a)In this following case the worst case T(n)=O(n)

For worst case if the element is present in the last position

then

Number of times line 5 will be executed is equal to N
Number of times line 6 will be executed is equal to N

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.