1
$\begingroup$

Consider the algorithm

procedure BS(a[1, ..., n] : array of n numbers)     if(n = 1) return;     if(n = 2 and a[1] > a[2])        swap(a[1],a[2]);        return;     s := floor(n/3)     BS(a[1, ..., n − s]);     BS(a[1 + s, ..., n]);     BS(a[1, ..., n − s]);     return; 

I'm trying to write a recurrence for a function $R(n)$ such that BS runs in $O(R(n))$ time on a size $n$ array. I'm not really sure how I can do that, as I don't entirely understand how the algorithm is working to compute the answer. Can someone perhaps outline what's necessary in order to come up with an accurate solution? In general, what steps should one take to ensure that the running type of some algorithm is captured?

  • 1
    Ignoring fractional parts, the algorithm is sorting the first two-thirds of the list, then the last two-thirds of the result, and finally the first two-thirds of *that* result. Thus, your recurrence is (ignoring floors) $$R(n)=3R\left(\frac{2n}3\right)\;.$$2012-12-17
  • 0
    Do we need to add the number of comparisons the algorithm is making (how many times it's swapping)?2012-12-17
  • 0
    The solution says that $$R(n) = 3R(\frac{2n}{3}) + 1$$I now understand how the first term was found, but the +1 term is confusing me. Is this the number of operations (one) when the algorithm works on an array of size n=1 or n=2?2012-12-17
  • 0
    @BailorTow You can. There is at most two comparisons and and one swap per recursive call, you can add 3 to Brian's answer.2012-12-17
  • 0
    @Code-Guru so, ignoring comparisons, we would have Brian's answer +1? Does (n==1)return; correspond to a base case? So that R(1) = 1?2012-12-17
  • 0
    @BailorTow There are two base cases. It looks like your text book is counting the number of swaps (which is reasonable for analyzing this algorithm), so $R(1) = 0$ and $R(2) = 1$.2012-12-17
  • 0
    @BailorTow Counting swap operations also means adding 1 to Brian's answer is correct, rather than adding 3 as I suggested.2012-12-17

0 Answers 0