CSCI 356: Design and Analysis of Algorithms

T (n) = T(1) for n = 1
aT(n/b)+f(n) for n > 1

Do the expansions (book calls this the substition method). The text notes,
it can be shown that

^log_ba

j=1 to k

^log_ba

Use this with the homework:
T(n) = 8 T(n/2) + n³
Hint: The solution contains a term cn³log₂n.

How does this compare?

T (n) = aT(n/b)+f(n)
T(n) = 8 T(n/2) + n³ so a = 8 and b = 2 and f(n)is n³

T(n) = n³[T(1) + u(n)] where u(n)= j=1 to k h(b^j) and h(n)= f(n)/n^log_ba

so looking at h(n), n³/n³ = 1. How nice h(n) = 1

so u(n) = j=1 to k 1 = k

but what is k? log₂n

We have T(n) = n³[T(1) + u(n)]

so T(n) = n³[T(1) + log₂n]

T(1) = 1 so T(n) = n³[ 1 + log₂n] = n³ + n³log₂n