HU Design of Algorithm and Data Analysis Worksheet

Hw2, due Thursday, September 231. S(n) = 3S( n3 ) + b.
(a) Use a recursion tree to show that S(n) = ⇥(g(n)), for some function g(n).
(b) Use induction to prove that S(n) = ⌦(g(n)).
2. T (n) = T (n 1) + log n. Assume that there is an appropriate base case.
(a) Draw a recursion tree for T (n). Identify its depth and the amount of work per level. Use
“exaggerate and simplify” to get an upper bound for T (n), and then underestimate and simplify
to get a matching lower bound. (Always using Theta notation). Your bound should be in a form
that is easily recognizable (and easy to compare to simple functions like linear, quadratic, etc).
(b) Derive the same upper bound for T (n), by induction.
p
3. Solve T (n) = T ( n) + 1, using a change of variables: n = 2m . After doing that, transform the
recurrence again, into something that you can solve easily.
To warm up, consider the following question. (Don’t submit an answer for the warmup)
Think of an abstract recursive algorithm that operates on a n ⇥ n matrix: It does non-recursive
work proportional to the number of elements in the matrix (say just n2 work), and then recurses
on each of the four quadrants. Assume that quadrants are nicely defined.
This could be expressed as S(n) = 4S( n2 ) + n2 , meaning the parameter used in S to describe the
problem is the matrix side length.
But suppose that we hadn’t thought of doing that, and instead we expressed the time complexity
2
as T (n2 ) = 4T ( n4 ) + n2 . Here, the parameter used for the problem size is the total number of
elements. In this case, because this parameter in T is a function of n (other than just n itself), we
don’t really have a direct method to deal with it. But we could set m = n2 , so T (m) = 4T ( m4 ) + m.
What’s the solution in each case (in terms of n)? It should be the same.
Besides that, the lesson here is that there can be multiple ways to quantify a problem size and
recurse accordingly, e.g. S(n) vs T (n2 ). You’ll need to consider this after you apply the change of
variables as suggested above for the actual homework problem.
4. Use the master method for the following (state case or explain what dominates, and state the
answer), or explain why it’s not possible.
(a) T (n) = 10 · T ( n3 ) + ⇥(n2 log5 n).
(b) T (n) = 256 · T ( n4 ) + ⇥(n4 log4 n).
(c) T (n) = T ( 19n
) + ⇥(n2 ).
72
(d) T (n) = n · T ( n2 ) + nlog2 n .
(e) T (n) = 16 · T ( n4 ) + n2 .
(f) T (n) = 3 · T ( n2 ) + n2 .
(g) T (n) = T ( nn 1 ) + 1.
p
n
(h) T (n) = 4 · T ( 16
) + n.