Lolz Easy Shit

Comp 2080 Assignment 3
Jesus
March 14, 2010
1

---

1.
Observe that
n?1
T (i) = T (0) + T (1) + · · · + T (n ? 1)
i=0
= T (n ? 1) + T (n ? 2) + · · · + T (0)
n?1
=
T (n ? 1 ? i)
(1)
i=0
Therefore,
n?1
T (n) =
[T (i) + T (n ? 1 ? i) + 1]
i=0
n?1
=
[T (i) + T (i) + 1]
by (1)
i=0
n?1
= 2
T (i) + n
(2)
i=0
If we replace n with n ? 1 in (2), we have
n?2
T (n ? 1) = 2
T (i) + n ? 1
(3)
i=0
Subtracting (3) from (2) yields
T (n) ? T (n ? 1) = 2T (n ? 1) + 1
T (n) ? 3T (n ? 1) = 1
(4)
which results in the following collapsing sum
T (n) ? 3T (n ? 1) = 1
3T (n ? 1) ? 9T (n ? 2) = 3
9T (n ? 2) ? 27T (n ? 3) = 9
.
.
.
3n?1T (1) ? 3nT (0) = 3n?1
Simplifying, we have
n?1
T (n) =
3i
since T (0) = 0
i=0
1 ? 3n+1
=
? 3n
1 ? 3
3n ? 1
=
2
2

---

Alternatively, we solve the non-homogeneous equation (4).
Since the Auxiliary Equation is r ? 3 = 0, which has the single root r = 3, the general solu-
tion for the homogeneous part is given by
T (n) = c13n
If we make the guess T (n) = an + b for the non-homogenous part, we ?nd that
1 = an + b ? 3(a(n ? 1) + b)
= an + b ? 3an + 3 ? 3b
= ?2an + 3a ? 2b
from which it follows that
a = 0
b = ?1/2
Putting this into the general solution for the homogeneous part, we have the general solution
T (n) = c13n ? 1/2
Substituting in T (0) yields
0 = c1 ? 1/2
c1 = 1/2
Thus, the ?nal solution is
3n ? 1
T (n) = 3n/2 ? 1/2 =
2
which matches the solution we found using the collapsing sum. Furthermore,
T (1) = 3T (0) + 1 = 1 = 3?1
2
T (2) = 3T (1) + 1 = 4 = 9?1
2
Thus, it appears this solution is correct.
3

---