1)

The number of times the loop body is executed is:

  n-1       n-1           n-1
  -----   -----         -----
  \       \             \
   \       \   1    =    \     (n-1) - (i+1) + 1      
   /       /             /
  /       /             /
  -----  ------         -----
  i=0     j = i+1       i=0

Since (n-1) - (i+1) + 1 = (n-1) - i we get that the number of times the loop
body is executed is:  (n-1) + (n-2) + ... + 0 = n(n-1)/2 = n^2/2 - n/2 

Hence the time complexity is Theta(n^2).

2a)

In all of the below lim is used for the limit as n approaches infinity:

    6n^2
lim --------    = 0
    (n^2) log n

Hence (n^2) log n is asymptotically faster growing than 6n^2.  Thus

  6n^2 = O(n^2 log n),  6n^2 != Omega(n^2 log n), 6n^2 != Theta(n^2 log n)

  A1 is the faster algorithm.

2b)

In all of the below lim is used for the limit as n approaches infinity:

    3/2 n^2 + 7n - 4          3n + 7            3
lim ----------------  = lim -----------  = lim ----  = 3/16
         8n^2                 16 n              16


Hence these two functions grow at the same asymptotic growth rate, though
T1 has the smaller constant.  Thus

  T1(n) = O(T2(n)),  T1(n) = Omega(T2(n)) and T1(n) = Theta(T2(n))

  A1 is the faster algorithm since T1 has the smaller constant.

2c)

In all of the below lim is used for the limit as n approaches infinity:

     n^4
lim --------    = infinity
    n^3 log n

Hence n^4 is asymptotically faster growing.  Thus

  n^4 != O(n^3 log n),  n^4 = Omega(n^3 log n), n^4 != Theta(n^3 log n)

  A2 is the faster algorithm.

3a)
This is false as demonstrated by the counterexample, f(n)=n and g(n)=n^2.
Note that n = O(n^2) but n^2 != O(n).

3b)

We prove this is true.  The key observation is that

   f(n) + g(n) <= 2 max(f(n) + g(n)) for all n

Thus by letting n_0 = 1 and c = 2 we get the required conditions to have
that f(n) + g(n) = O(max(f(n),g(n))

3c)

We prove this is true.  To prove  If p then q we assume p is true and show
that q must follow.  Thus we assume that f(n) = Omega(g(n)).  By the definition
of Omega we have that constants c and n_0 exists such that

   f(n) >= c g(n) for all n >= n_0    (*)

We must show that there exists constants n'_0 and c' for which

   g(n) <= c' f(n) for all n >= n'_0

Solving for f(n) in the above, we get the equivalent requirement that

   f(n) >= 1/c' g(n) for all n >= n'_0

By letting 1/c' = c (so let c' = 1/c) and n'_0 = n_0 this is clearly true
since it is the same as the equation marked by a (*)

(b,c) True, since n^2 (the dominate term on the left) asymptotically grows like n^2 and hence it is Omega(n^2) and also Theta(n^2). faster growing than n log n and hence not upperbounded by it.

(d) False since n log n (the dominate term on the left) is not asymptotically upperbounded by n.

(e) True, since the dominate term on the left, 10 SQRT(n), is asymptotically upperbounded by n.

(f,g) False, since the dominate term on the left, SQRT(n), is not asymptotically upperbounded by n. See the class notes where we showed that that lim as n -> infinity of log n / SQRT(n) = 0 giving that SQRT(n) is asymptotically faster growing.

(h) False, since the dominate term on the left, SQRT(n), is asymptotically faster slower growing than n.

(i) True, since the dominate term on the left, 2 SQRT(n), grows asymptotically at the same rate as SQRT(n).

(j) True, since the dominate term on the left, SQRT(n), is asymptotically faster growing than 1.

(k) True, since the dominate term on the left, SQRT(n), is asymptotically faster growing than log n.

(l) False, since the dominate term on the left, SQRT(n), is asymptotically slower growing than n.

5)

Clearly T(1) = Theta(1).  The first loop used for splitting has time complexity
Theta(n) and the second has time complexity Theta(n^2).  

There are 2 recursive calls of size n/2.

Finally constant time (Theta(1)) is spent combining.  Hence we get the
recurrence.

  T(1) = Theta(1)
  T(n) = 2 T(n/2) + Theta(n^2) for n >= 2

By the master method we get that T(n) = Theta(n^2).  Hence this given algorithm
is a Theta(n^2) algorithm.

6a)

T(n) = c n log_2 n + n

We are going to exactly solve this recurrence when n is a power of 2.
There are log_2 n levels above the leaves each of which uses cn statements. 
Finally there are n leaves that use 1 step each.

To prove it is correct (for n a power of 2) we use induction on k = 0,1,2,... 
where n = 2^k.  So the base case is that T(1)=1 by the definition and our
formula also gives 1 since log_2 1 = 0.

inductive step:  Show if T(2^k) = c 2^k k + 2^k 
                      then T(2^{k+1}) = c 2^{k+1} (k+1) + 2^{k+1}

   Thus we assume that T(2^k) = c 2^k k + 2^k (this is our inductive hypothesis).
   By the given definition that T(n) = 2 T(n/2) + cn we have that

  T(2^{k+1}) = 2 T(2^k) + c 2^{k+1}

Then by applying the inductive hypothesis for T(2^k) and simplifying we get
the desired result that T(2^{k+1}) = c 2^{k+1} (k+1) + 2^{k+1}

6b)

The number of leaves is 4^{log_2 n} = 2^{2 log_2 n} = 2^{log_2 n^2} = n^2

T(n) = (SUM_{i=0 to (log_2 n) - 1} cn 2^i) + n^2 T(1) = cn(2^{log_2 n} - 1) + n^2

     = cn^2 - cn + n^2

     = (c+1) n^2 - cn

To prove it is correct via induction follow the same structure as in 6a above.

6c)

The number of leaves is 2^{log_4 n} = 4^{1/2 log_4 n} = 4 ^{log_4  n^{1/2}}
  =  sqrt(n)

T(n) = (SUM_{i=0 to (log_4 n) - 1} sqrt(n) + sqrt(n) T(1) 
 
     = sqrt(n) log_4 n + sqrt(n)

     = sqrt(n) (log_4 n + 1)


To prove it is correct via induction follow the same structure as in 6a above
except you will let n = 4^k.