Witam moim zadaniem jest pokazać że czas działania algorytmu heapsort wynosi O(n lg n).
Z pomocą google itp udało mi się dojść do pewnego rozwiazania.
Jesli ktos potrafilby wytlumaczyc mi dlaczego ta 2 jest pomijana w zapisie w ostatniej linijce ? bo ja napisalbym ze T1(n) = O(2n) ale widziałmm w teori, że wynosi właśnie O(n).Prawde mówiąc przy T2(n) rozumie wszytsko a przy T1(n) już nie bardzo.
Ostatecznie zapis bedzie wyglądał tak
T(n)=T1(n) + (n-1)*T2(n)= O(n) + (n-1)O(lg n) i teraz chciałbym by ktoś mi wytłumaczył jak to jest zrobione że ostateczny wynik tego zapisu wyniesie T(n) = O(n lg n) ?
