===========================================================================
CSC 236 Tutorial Solutions for Week 5 Winter 2012
===========================================================================
1. List and explain the steps used to analyze the time complexity of a
recursive algorithm-- provide as much detail as possible.
(a) Write a recurrence relation for T(n), the worst-case number of
steps taken by the algorithm on inputs of size n. This involves
defining n as an expression of the algorithm's parameters, then
analyzing the number of steps taken by the algorithm for various
input sizes-- with cases based on the algorithm's base cases and
general cases.
(b) Find upper and lower bounds on the values of T(n), i.e., functions
L(n) and U(n) such that T(n) (- \Omega(L(n)) and T(n) (- O(U(n))--
ideally, L(n) = U(n); otherwise, make them as close as possible to
each other.
In the absence of other information, the "repeated substitution"
method can be used to find a reasonable guess: start with an
expression for T(n) from the recurrence relation, with simplifying
assumptions (like ignoring floors and ceilings), and repeatedly
expand (substitute) into expressions T(...) on the right-hand side
until the pattern becomes obvious. From the expression after k
substitutions, work out how many substitutions are necessary to
reach a base case, plug in that value for k, and simplify.
(c) Prove T(n) (- \Omega(L(n)) and T(n) (- O(U(n)) for the bounds L(n)
and U(n) found in the previous step. If both bounds are simply
obtained from the result of performing repeated substitution, often
this will involve making small modifications to the exact
expression used (changing constant factors or adding low-order
terms)-- whatever is necessary to make the proofs work out.
This is done by complete induction on n, following the recurrence
relation for T(n).
Note that the final answer, the one that really matters, is the proof
of each bound on T(n) (step (c) above). The expression obtained by
repeated substitution is only the *starting* point for these proofs,
because it is an approximation only.
2. Consider the following recurrence relation.
{ 2 if n = 0, 1
T(n) = {
{ T(floor(2n/3)) + lg(n) if n > 1
Find upper and lower bounds on the value of T(n), using the Master
Theorem. Then try to find a tight bound.
This is a trick question, because the Master Theorem only applies to
recurrences where the extra work performed outside the recursive calls
takes time \Theta(n^d) for some constant d. Unfortunately, lg(n) is
*not* such a function...
Nevertheless, we can use the Master Theorem to obtain separate upper
and lower bounds on the value of T(n). Consider the following
recurrence relations.
{ 2 if n = 0, 1
L(n) = {
{ L(floor(2n/3)) + 1 if n > 1
{ 2 if n = 0, 1
U(n) = {
{ U(floor(2n/3)) + n if n > 1
Since 1 <= lg(n) <= n for all n > 1, it is easy to see that for all n,
L(n) <= T(n) <= U(n).
Applying the Master Theorem to L(n), we get a = 1, b = 3/2 and d = 0 so
a = b^d and L(n) (- \Theta(n^d log n) = \Theta(log n).
Hence, T(n) (- \Omega(log n).
In this case, it would be trivial to prove T(n) >= lg(n) by induction on
n >= 1-- it may seem that the inductive hypothesis is not necessary, but
it is to ensure that T(floor(2n/3)) is not negative.
{ Go over this proof at the end of you have time left-- but don't worry
about it if you don't. }
Applying the Master Theorem to U(n), we get a = 1, b = 3/2 and d = 1 so
a < b^d and U(n) (- \Theta(n^d) = \Theta(n).
Hence, T(n) (- O(n).
Again, it is trivial to prove T(n) <= 2 n by induction on n >= 1--
making use of the fact that lg(n) <= n for all n >= 1.
{ Go over this proof at the end of you have time left -- but don't worry
about it if you don't. }
Unfortunately, we have reached the limit of what can be learned by
applying the Master Theorem-- there is no way to make the bounds any
tighter.
{ Well, that's not quite true: if we remember that lg(n) is o(n^c) for
any realy number c > 0 (from calculus), then we can prove that T(n) is
O(n^c) for any real number c > 0. But that still leaves a gap between
the upper and lower bounds. }
In order to get a tight bound, we need to use something like the
repeated substitution method. We will need to use the following facts
about logarithms-- it is assumed that you are aware of these properties,
and you are allowed to make use of them in your own work. For all real
numbers x, y > 0, and all bases b > 1:
- log_b(x/y) = log_b(x) - log_b(y)
- log_b(xy) = log_b(x) + log_b(y)
- log_b(x^y) = y log_b(x)
Repeated substitution for T(n):
T(n) = T(2n/3) + lg(n)
= T(2(2n/3)/3) + lg(2n/3) + lg(n)
= T((2/3)^2 n) + 2 lg(n) + lg(2/3)
= T((2/3)^3 n) + lg((2/3)^2 n) + 2 lg(n) + lg(2/3)
= T((2/3)^3 n) + 3 lg(n) + 3 lg(2/3)
= T((2/3)^4 n) + lg((2/3)^3 n) + 3 lg(n) + 3 lg(2/3)
= T((2/3)^4 n) + 4 lg(n) + 6 lg(2/3)
after i substitutions,
= T((2/3)^i n) + i lg(n) + (i (i-1) / 2) lg(2/3)
T() "disappears" from the right-hand side when (2/3)^i n = 1, i.e.,
i = log_{2/3}(1/n) = log_{3/2} n. For this value of i,
T(n) = T(1) + log_{3/2} n lg(n)
+ (log_{3/2}(n) (log_{3/2}(n) - 1) / 2) lg(2/3)
Based on this, we expect that T(n) (- \Theta(log^2 n). Proving this,
however, becomes a little tricky...