Мой учитель просит нас доказать, что если f (n) = Theta (n log ^ kn), T (n) = aT (n / a) + f (n), то рекурсия имеет решение T (n ) = Theta (n log ^ {k + 1} n).
Мое решение основано на методе подстановки:
Слишком много математических формул, поэтому я обрезал картинку. Изображения показаны следующим образом.
В заключение, T (n) = Theta (n log ^ (k + 1) n) , Это правильно?