Calculate T(n) and the order of complexity Algorithm-3 recursive function MaxSum

Question

Calculate T(n) and the order of complexity

Algorithm-3 recursive function MaxSumCKIL. Ul: array of integer, L, U: integer) if L> U en return 0 /k zero- element vector if L-U then. return max(0,XILD one-element vector A is XLL...M], B is XLM+1..U] Find max crossing to left sum 30: maxToLeft for I BM downto L do sum suman XII maxToLeft max(maxToLeft,sum) Find max crossing to right sum 0: maxToRight-0 for ISM-1 to U sum sum 10 maxToRight max(maxToRight, sum 11 12 maxCrossing maxToLeft maxToRight 13 maxInA maxSumCK, L, M) 14 maxInB max Sum(X, M+1,U) 15 return max(maxCross maxInA, maxInB ing,

Explanation / Answer

MaxSum() is a recursive method and time complexity can be expressed as following recurrence relation.

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

This is similar to Merge Sort and can be solved either using Master Theorem OR Recurrence Tree method.

The time complexity is O(nlogn)

Proof to show its O(nlogn):

Master Method is a direct way to get the solution. For the below equation we have 3 cases,

There are following three cases:
1. If f(n) = (nc) where c < Logba then T(n) = (nLogba)

2. If f(n) = (nc) where c = Logba then T(n) = (ncLog n)

3.If f(n) = (nc) where c > Logba then T(n) = (f(n))

For the recurrence equation, T(n) = 2T(n/2) + (n).
It falls in case 2 as c is 1 and Logba] is also 1. So the solution is (n Logn)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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