równania rekurencyjne rozwiązywanie

Question

Witam 

Od dłuższego czasu nie mogę zrozumieć rozwiązywania równań rekurencyjnych

T(n)=T(n/4)+cn

T(1)=c  

Jak rozwiązać to metoda iteracyjną i co oznacz to c w równaniu? 

Answer 1

Nikt Ci lepiej nie wytłumaczy niż M. Zelent.

https://www.youtube.com/watch?v=jNi_X5bvmQ0

Answer 2

T(n)=T(n/4)+cn

T(n)=T(n/4)+T(1)n

T(1)n+T(n/4)=T(n)

T(1)n+T(n/4)=T(n)

T(1)n=T(n)-T(n/4) | /n

T(1)=(T(n)/n-T(n/4))/n

c=(T(n)-T(n/4))/n

 

 

Answer 3

W zeszycie mam to tak rozwiązane ale nie kminie o co chodzi.

Czy ktoś potrafi mi to wytłumaczyć?

Answer 4

WItam mam podobny problem do kolegi z tym że chciałbym zrozumieć metode rozwiązywania rekurencji chodzi mi o metodę podstawiania. Prosze mi wytłumaczyć w jaki sposób rozwiązano tą nie równość (wiem że to ma coś wspólnego z indukcją matematyczną ale tego nie widzę) 

Z góry dziękuje za poświęcony czas w tłumaczeniu.