finding the closed form of $ T(n) = 4T(n/4) + 5n$

Question

I am trying to use "telescoping" demonstrated in this tutorial https://www.youtube.com/watch?v=lPCS2FFyqNA to solve this recurrence relation.

I started it off below, but quickly lost my way. Might anyone show the process for breaking down this recurrence relation, $ T(n) = 4T(n/4) + 5n$ into a closed form?

$T(n) = 4T(n/4) + 5n $

$T(n-1) = 4T((n-1)/4) + 5n - 5$

$T(n-2) = 4T((n-2)/4) + 5n - 10 $

$....$ $T(n) = ???$

I know we would cancel out the terms on the left and the right side of the $=$ but because it's divided by 4, I'm getting a bit lost...

Thank you

Is N any integer, or is it any integer div. by 4? – Feb 12 '20 at 07:23 — , Feb 12 '20 at 07:23

score 1 · Accepted Answer · answered Feb 12 '20 at 08:54

1

Hint.

Taking $m = 4n$

$$ T(4m)=4T(m)+20m $$

and now

$$ T\left(4^{\log_4(4m)}\right)=4T\left(4^{\log_4(m)}\right)+20m $$

calling $\mathcal{T}(\cdot)=T(4^{(\cdot)})$ and $z = \log_4 m$

$$ \mathcal{T}(z+1)=4\mathcal{T}(z)+20\times 4^z $$

with solution

$$ \mathcal{T}(z) = \left(5z+C_0\right)4^z $$

now from $z$ to $m$.

answered Feb 12 '20 at 08:54

Cesareo

33,252

Thank you @Cesareo... I'm a bit confused in how you found $4{^/log(4m)}$ can you explain that part. Thanks! – Katie Melosto Feb 12 '20 at 14:13
1

With positive $m$ we have $4m=4^{\log_4(4m)}$ – Cesareo Feb 12 '20 at 14:16

finding the closed form of $ T(n) = 4T(n/4) + 5n$

1 Answers1