Practice Problem Answers - recurrences and asymptotic notation

These are just the answers, so that you can verify for yourself that you got the right answer.

Problem 2-2

Table entries in left to right order for each row:

a.

yes, yes, no, no, no

b.

yes, yes, no, no, no

c.

no, no, no, no, no

d.

no, no, yes, yes, no

e.

yes, no, yes, no, yes

f.

yes, no, yes, no, yes

Problem 4-1

a.

(use case 3 of the master theorem)

b.

(use case 3 of the master theorem)

c.

(use case 2 of the master theorem)

d.

(use case 3 of the master theorem) of the master theorem)

e.

(use case 1 of the master theorem)

f.

(use case 2 of the master theorem)

g.

(iteration method; see page 156 for details)

h.

. Note that you might iterate the recurrence to figure out that this is the proper bound; the constant 1 is added each time we iterate, so that we get for larger and larger k. This will stop once gets down to about , since at that point is about 1. Solving gives , which suggests that we'll add 1 about times before the problem size gets too small to crank the recurrence anymore.

Use the substitution method to prove this bound is correct. First show that for n>2. For the base case, pick c large so that this is satisfied for (we need this so that any recurrences that start with larger n (that is, n>4 so that ) will eventually depend on this base case, rather than falling through to some smaller n for which we don't have any bound). Now, assume this bound holds for values less than n, and show for n. Substituting into the recurrence, we get:

Pick c>1, so that we can drop the term and get our desired conclusion:

So, .

Since we want a bound, we also need a lower bound on . We want to show that . Similar to the above, for the base case pick c small enough so that this bound holds for . Now, assume the bound holds for values less than n and show for n. Substituting into the recurrence:

Pick c<1, so that we can drop the term and get our desired conclusion:

So, . Combining this with the above, .