Предполагая, T(n) <= n^1.5 является правильным путем.При этом мы можем иметь:
T(n) <= 6 ( n^1.5 / 3^1.5 ) + 3n = (6 / 3^1.5)* n^1.5 + 3n.
6/3^1.5 равно 5,1 ... но сейчас позвольте назвать его a.Итак, мы имеем: a*n^1.5 + 3n.
Нам нужно доказать, что c> 0 при n0> n c*n^1.5 > a*n^1.5 + 3n.сначала пусть делится на n: c*n^0.5 > a*n^0.5 + 3, что дает: (c-a)*n^0.5 > 3.
Отсюда ясно, что вы можете выбрать любые c > a и n > 9, так что это будет верно.
Подводя итог: мы получили T(n) больше T'(n) = (6/3^1.5)*n^1.5 + 3n и доказали, что для c > 6/3^1.5 и n > 9 T(n) < cg(n) where g(n) = n^1.5