Recurrence
Document last modified: 

Give the recurrence for the following algorithms:

  1. BinarySearch (A, key, low, high)
    1 if (low > high) return -1;
    2 int mid=(low+high)/2;
    3 if (key == A[mid]) return mid;
    4 if (key > A[mid])
    5           return BinarySearch(A, key, mid+1, high);
    6 else    return BinarySearch(A, key, low, mid-1);
    T(1) = b

    T(n) = T(n/2) + b for all n>1

     

  2. Merge_Sort (A, p, r)
    1 if p < r then
    2    q ← floor ((p + r) / 3)
    3    Merge_Sort (A, p, q)
    4    Merge_Sort (A, q + 1, 2*q)
    5    Merge_Sort (A, 2*q + 1, r)
    6    Merge (A, p, q, 2*q, r)
    T(1) = b

    T(n) = 3(n/3) + bn for all n>1

     

    AddPowers( n )
        if n = 1 return 1

        int sum=AddPowers(n-1)

        for i=1 to n do

            for j = 1 to n do

                 sum = sum + i + j;

        return sum;           

  3.  
    T(1) = b

    T(n) = T(n-1) + bn2 for all n>1

     

  4. Insert(a, L)
        if L = empty then return [ a ]

        if a > head(L) then return head(L)::insert( a, tail( L ) )

        return a::L;
    T(1) = b

    T(n) = T(n-1) + b for all n>1

    Sort( L )
        if L = empty then return L

        return insert( head( L ), sort( tail( L )));
    T(1) = b

    T(n) = T(n-1) + bn for all n>1