CODEWITHSUNDEEP
algorithmcomplexity-theory
Joe Knuth
Joe Knuth

Reputation: 13

Finding the asymptotic amount of comparisons performed by an algorithm

I have been given the following algorithm:

Supersort(A, i, j):
   if(j = i): return
   if(j = i + 1):
      if(A[i] > A[j]):
         swap(A[i], A[j])
   else:
      k = floor of ( (j-i+1)/3 )
      Supersort(A, i, j-k) // sort first two thirds
      Supersort(A, i+k, j) // sort last two thirds
      Supersort(A, i, j-k) // sort first two thirds again

And I really am not sure how to analyze how many comparisons in the worst case this algorithm would make. I don't want the answer given to me, I just don't even know how to get started solving this problem. Thanks for any help

Upvotes: 1

Views: 63

Answers (1)

Hikmat Farhat
Hikmat Farhat

Reputation: 592

Typically when you have a recursive function the first thing you do is obtain a recurrence relation. In your case let T(n) be the cost of supersort when the input is of size n. What is that equal? The first two if stmts are just constants and the else costs T(2n/3)+T(n/3)+T(2n/3) then

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

Then you solve that recurrence.

Correction: in the three cases you use 2/3. I thought one of them is 1/3. In that case the recurrence is even simpler and can be solved using the master theorem

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

Upvotes: 1

Related Questions