a. Write down the recurrence relation for the running time of Unusual. You are w

Question

a. Write down the recurrence relation for the running time of Unusual. You are welcome to ignore floors and ceilings, but make sure you write the base case also, expicitly.

b.  Solve the recurrence using the Master Theorem and find the running time of UNUSUSAL.

CRUEL A 1 n if n >1 RUEL n/2]) CRUEL(ACn/2 +1.. n]) UNUSUAL 1... n UNUSUAL 1..n if n 2 if A[1] A12] (the only comparison!) swap A[1] AC2] else (swap 2nd and 3rd quarters) for i 1 to n/4 swap Ali n/4] Ali n/2] UNUSUAL GAL1 n/2]) recurse on left half UNUSUAL CAIn/2 1.. n]) (recurse on right half)) UNUSUAL 1..3n/4]) recurse on middle half

Explanation / Answer

Solution:

a)

The base case for the given algorithm is

if n=2

if A[1]> A[2]

swap(A[1]<=>A[2])

So recurrence will be for Unusual(A[1...n/2]) ---------- n/2, because this statement is dividing the given array into left half.

Unusual(A[n/2+1...n]) ---------- n/2, because this statement is dividing the given array into right half.

Unusual(A[n/4+1...3n/4]) ---------- 3n/4-n/4= 2n/4= n/2.

So total three recursive calls.

This means that T(n)= 3T(n/2)+ n

b)

Using Master theorem the solution is

a= 3 and b= 8 and f(n)= n

n^(logba)= n^(log23)= n

So this is case 2 of master theorem,

So T(n)= n log n.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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