Prośba o wytłumaczenie zadania maturalnego - informatyka

Question

https://www.cke.edu.pl/images/_EGZAMIN_MATURALNY_OD_2015/Materialy/Zbiory_zadan/Matura_Zbi%C3%B3r_zada%C5%84_Informatyka.pdf

Proszę o wytłumaczenie mi zadania 7.3 ze strony 21. Odpowiedź to 49 a ja nie wiem w jaki sposób ją uzyskać.

Answer 1

No tworzysz sobie układ rekurencyjny

T(n) = 2T(n/2) + n-1

T(1) = 0

 

Po rozwiązaniu dostajesz

T(n) = 1 + n*(log2(n) - 1)

i podstawiasz pod n rozmiar tablicy czyli 16

i dostajesz T(16) = 49

Comments

Można trochę jaśniej? :D