Sample problems for tutorial #4

  1. Give a recurrence relation for the running time of the following algorithm as a function of n = last - first + 1. To simplify your answer, do not specify the floors and ceilings in your recurrence.
    Algorithm TurtleSort(A, first, last)
    
    if (last - first ≤ 2) then
        if (last - first ≤ 1) then
            if (A[first] > A[first+1]) then
                swap (A[first], A[first+1])
            endif
    
            if (last - first = 2) then
                if (A[last-1] > A[last]) then
                    swap (A[last-1], A[last])
                endif
                if (A[first] > A[first+1]) then
                    swap (A[first], A[first+1])
                endif
            endif
        endif
        return
    endif
    
    q1 ← floor of (3*first +   last)/4
    q2 ← floor of (  first +   last)/2
    q3 ← floor of (  first + 3*last)/4
    
    turtleSort(A, first, q2)
    turtleSort(A, q1, q3)
    turtleSort(A, q2, last)
    turtleSort(A, q1, q3)
    turtleSort(A, first, q2)
    turtleSort(A, q1, q3)
    

  2. Using the guess-and-test method, prove that the function T(n) defined by the recurrence relation

    is in O(4n).
  3. Let T(n) be defined by T(n) = T(⌊n/2⌋) + n2 if n ≥ 2, with T(1) = 1. Use the Master theorem to get a upper bound on T(n).
  4. Prove upper and lower bounds on the function T(n) defined by T(n) = 6T(⌊n/2⌋) + 16T(⌊n/4⌋) + 2n3 when n ≥ 4, with T(1) = T(2) = T(3) = 1.