1. recurrences

trying to make sure i'm doing this right...

solve the recurrence in theta notation
assume base case T(x) = 1 for x <= 5

for T(n) = 4T(n/5) + n , is the answer T(n) = Theta(2n) ?

2. Originally Posted by inneedofhelp
trying to make sure i'm doing this right...

solve the recurrence in theta notation
assume base case T(x) = 1 for x <= 5

for T(n) = 4T(n/5) + n , is the answer T(n) = Theta(2n) ?
First of all $\displaystyle T(n) = \Theta (2n)$ is the same thing as $\displaystyle T(n) = \Theta (n)$.

Now:

$\displaystyle T(n) = 4 + \sum_{k=0}^{\lfloor log_5(n)-1 \rfloor } n(4/5)^k$

Which is obviously $\displaystyle \Theta (5n)=\Theta (n)$

RonL

3. ok, so if I have

T(n) = T(n-3) + n^3

then i'll have

n^3 + (n-3)^3 + (n-6)^3 + (n-9)^3 + ... + 1^3

so

I'll have n-3 terms and max of n^3 at each one, so is this Theta(n^4) ?

4. Originally Posted by inneedofhelp
ok, so if I have

T(n) = T(n-3) + n^3

then i'll have

n^3 + (n-3)^3 + (n-6)^3 + (n-9)^3 + ... + 1^3

so

I'll have n-3 terms and max of n^3 at each one, so is this Theta(n^4) ?
Yes (assuming you have suitable initial conditions), though I'm note sure the explanation of why its $\displaystyle \Theta (n^4)$ is acceptable. I would use upper and lower bounds derived from an integral approximation to the sum.

RonL