Chapter 1: A Recurrance Solution

Analysis of Recursive Programs

• (a) The solution contains a term cn^{log₂ 3}
• (b) The solution contains a term cn^{log₂ 3}
• (c) The solution contains a term cn³log₂n

T(n) = 3T(n/2) + n.
Given the hint, a good guess is T(n) < cn^{log₂ 3} + bn
Even better: T(n) < cn^{log₂ 3} - 2n
For how this good guess came about, see below

Prove using induction:

PROOF:

Base:
T(1) = 1 by definition
T(1) < c*1^{log 3} - 2*1 (assume logs are always base 2) implies
1      <       c - 2       implies
3      <       c            (OK, remember this - use for c)

Induction hypothesis:
Assume THM is true: T(n) = 3T(n/2) + n < 3n^{log₂ 3} - 2n for all n < n'.

Induction step:

Suppose n is greater than n', let n = n' + 1

then, T (n) = 3T(n/2) + n (by definition of T(n))

since n/2 < n', by induction hypothesis, T (n/2) = 3(n/2^{log₂ 3}) - 2(n/2)

Hence, by induction on n

T(n) < 3n^{log₂ 3} - 2n

is true for all n > 1.

and T(n) is O(n^{log₂ 3})

More on the handout

Here I will consider the recurrance relation:

Suppose
T(1) = 1
T(n) = 3T(n/2) + n
then
R(0) = 1 and
R(k) = 3R(k-1) + 2^k

With the hint that there is a term cn^{log₂ 3}. With n=2^k, substituting for n, this looks like
c(2^k)^{log₂ 3}
= c(2^{log₂ 3})^k
= c * 3^k

With the hint, we expected something like cn^{log 3} + bn.
So, a guess of R(k)= c * 3^k + b* 2^k looks like the R(k) expression.

Let's try this R(k)= c * 3^k + b* 2^k . (I.E., does it work for our definition of R(k)?)

R(k)                  = 3R(k-1) + 2^k
c * 3^k + b* 2^k =? 3(c * 3^k-1 + b* 2^k-1) + 2^k

c * 3^k = 3(c * 3^k-1) so take this off of both sides...        and 3(b* 2^k-1) is 3*1/2 (b* 2^k)

OK, this recurrance relation guess (3n^{log₂ 3} - 2n) looks good - let b = -2. Proof by induction (done above)