[ChcialbymKubekFaktow]

Mirki moje droge, mam pytanie. Próbuję rozwiązać zadanie jak na screenie. Wyszło mi, że postacią ogólną równania jest T(n) = n2^n. Zrobiłem tezę i dowód indukcyjny. Nie wiem jednak jak przekształcić mój wynik na podaną formę T(n) = nlgn. Czy ktoś byłby tak miły i mnie jakoś naprowadził? #matematyka

[s.....e]

Może po prostu z tego, że jeśli x = 2^k to k = log_2(x)

[michalo94]

@ChcialbymKubekFaktow: Podstaw n=2^k. Wtedy lgn=lg2^k=k, a 2^k=n.
Czyli masz T(2^k)=k2^k=nlg(2^k)=nlg(n)
Dla n=2 się zgadza, a co z resztą?
2T(n/2)+n=nlg(n/2)+n=2^klg(2^(k-1))+2^k=(k-1)2^k+2^k=k2^k=nlg(n)

[LeD7]

@ChcialbymKubekFaktow: Jeżeli lg=log2, to T(2^k)=2^k log2 2^k=k2^k