===========================================================================
CSC 236           Homework Exercise 3 -- Sample Solutions       Winter 2008
===========================================================================


1.  For this algorithm, n = y (the variable that gets smaller from one call
    to the next).  Base case: T(0) = 3 (one step for '==', 'if', 'return').
    General case: T(n) = 5 ('if' statements and associated comparisons)
    + 6 (worst-case arithmetic in recursive call, assignment to t, return)
    + T(floor(n/2)) (recursive call) -- when n even, n/2 = floor(n/2);
                                        when n odd, (n-1)/2 = floor(n/2).

    All together:
        T(0) = 3,
        T(n) = 11 + T(floor(n/2))  \-/ n >= 1.


2.  In repeated substitution, ignore floor/ceiling.

        T(n) = 2 T(n/4) + n - 1  [1 substitution]
             = 2 (2 T(n/16) + n/4 - 1) + n - 1
             = 4 T(n/16) + n/2 + n - 3  [2 substitutions]
             = 4 (2 T(n/64) + n/16 - 1) + n + n/2 - 3
             = 8 T(n/64) + n + n/2 + n/4 - 7  [3 substitutions]

    after i substitutions, we expect:

        T(n) = 2^i T(n/4^i) + n (1 + 1/2 + ... + 1/2^{i-1}) - (2^i - 1)
             = 2^i T(n/4^i) + n (1 - 1/2^i) / (1 - 1/2) - 2^i + 1
             = 2^i T(n/4^i) + 2n (1 - 1/2^i) - 2^i + 1

    base case reached when n/4^i = 1, i.e., i = log_4 n -- can't use base
    case 0 directly because n/4^i > 0, \-/ i (- N:

        T(n) = 2^{log_4 n} T(n/4^{log_4 n}) + 2n (1 - 1/2^{log_4 n})
                 - 2^{log_4 n} + 1
             = n^{log_4 2} T(1) + 2n (1 - 1/n^{log_4 2}) - n^{log_4 2} + 1
             = n^{1/2} (2 T(0) + 1 - 1) + 2n (1 - 1/n^{1/2}) - n^{1/2} + 1
             = 2 sqrt(n) + 2n - 2 sqrt(n) - sqrt(n) + 1
             = 2n - sqrt(n) + 1