Rozwiązać następujące równania rekurencyjne Michał: Rozwiązać następujące równania rekurencyjne: b) T(1)=2 T(n)=T(ⁿ₂)+2 n=2^m T(2^m)=T(2^m−1)+2 <=> S(m)=S(m−1) S(m)=S(m−1)+2=S(m−2)+4=S(m−3)+6=...=S(m−k)+2k=...^m=k=S(m−m)+2m=S(0)+2m= ? Tutaj się zaciąłem, ponieważ nie wiem ile powinno wynosić S(0), pomoże ktoś ?

jc: S(m)=T(2^m) jak się domyślam, a czego nie napisałeś S(0)=T(2⁰)=T(1)=2

Michał: ok, dzięki

Mariusz: Analizujesz złożoność jakiegoś algorytmu rekurencyjnego ? Zapisz swój algorytm w równoważnej postaci iteracyjnej wtedy może łatwiej będzie ci oszacować złożoność Zadanie bonusik ile pamięci będzie potrzebował algorytm rekurencyjny (rekurencja korzysta za stosu dlatego jeśli nie potrafimy zastąpić rekurencji za pomocą instrukcji iteracyjnej to jawnie korzystamy ze stosu) Niedawno widziałem podobną rekurencję dla algorytmu minmax metodą divide et impera Złożoność wyszła O(n)

Mariusz: Twoja rekurencja to złożoność wyszukiwania binarnego zatem otrzymamy O(logn) ale gdybyśmy mieli rekurencję

	n
T(n)=2T(		)+2
	2

to otrzymalibyśmy złożoność liniową O(n)