Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the algorithm

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

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?

share|cite|improve this question
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)\;.$$ – Brian M. Scott Dec 17 '12 at 1:17
Do we need to add the number of comparisons the algorithm is making (how many times it's swapping)? – Bailor Tow Dec 17 '12 at 1:23
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? – Bailor Tow Dec 17 '12 at 1:31
@BailorTow You can. There is at most two comparisons and and one swap per recursive call, you can add 3 to Brian's answer. – Code-Guru Dec 17 '12 at 1:33
@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? – Bailor Tow Dec 17 '12 at 1:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.