Пункт 8

Мастер-теорема

Пусть имеется рекуррентное соотношение:

T(n)={[a⋅T(n/b)+O(nc),,n>1],[O(1),,n=1])

Где a∈ℕ,b∈ℝ,c∈ℝ+,b>1

Тогда:

T(n)={[O(nc),c>(log_b)(a)],[O(nc*(log_)(n)),c=(log_b)(a)],[O(n(log_b)(a)),c<(log_b)(a)])

Доказательство

TODO

пока что мне лень его ботать, оно есть тута: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0