Write pseudocode for a divide-and-conquer algorithm for finding the position of

Question

Write pseudocode for a divide-and-conquer algorithm for finding the position of the largest clement in an array of n numbers. What will be your algorithm's output for arrays with several elements of the largest value? Set up and solve a recurrence relation for the number of key comparisons made by your algorithm. How does this algorithm compare with the brute-force algorithm for this problem? Write pseudocode for a divide-and-conquer algorithm for finding values of both the largest and smallest elements in an array of n numbers. Set up and solve (for n = 2^k) a recurrence relation for the number of key comparisons made by your algorithm. How does this algorithm compare with the brute-force algorithm for this problem?

Explanation / Answer

1) a) largest(array,length)

begin

max=0;

for i from 1 to length

if array[i]>array[i-1]

max=i

end

b) first largest number wiill be output

c) O(n), as we make n comparisions. T(1)=0 and T(n)=T(n-1)+1 if n>1

d) This is a brute force method as we compare each and every element

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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