Application: Problem 5t You are given following two recursive algorithms to dete

Question

Application: Problem 5t You are given following two recursive algorithms to determine maximum element in a given integer array A a) b) Write a recurrence relation for T(n) which counts number of comparisons in each algorithm Determine complexity of each growth function T(n) (you may use Master theorem if it is applicable for solution) Which algorithm is more efficient? c) int max1(int Allleft,right) //array A with size right-left+1 int max2(int A[], left, right) if(leftm2) return m1 return m1 else else return m2 return m2 return A[left] return A[left]

Explanation / Answer

a) Recurrence Relation for 1st algorithm is

T(n)= T(n-1) + c

And,

Recurrence Relation for 2nd algorithm is

T(n)= T(n/2) + c

b) Time Comlexity for 1st algorithm

T(n) = T(n-1) + c

= T(n-2) + c +c

= T(n-3) + c + c + c

= T(1) + c +c + ..... + c

= n*c

= O(n)

Time Comlexity for 2nd algorithm

T(n) = T(n/2) + c

=T(n/22) + c + c

=T(n/23) + c + c + c

= ..............

= c +c + c+......+ c (log2n times)

= c* log2n

=O(log2n)

c) second algorithm is more efficient as it takes lesser time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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