1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Is N any integer, or is it any integer div. by 4? $\endgroup$
    – user721016
    Feb 12 '20 at 7:23
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you @Cesareo... I'm a bit confused in how you found $4{^/log(4m)}$ can you explain that part. Thanks! $\endgroup$ Feb 12 '20 at 14:13
  • 1
    $\begingroup$ With positive $m$ we have $4m=4^{\log_4(4m)}$ $\endgroup$
    – Cesareo
    Feb 12 '20 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.