Как решить рецидивы с большой тэ, а не с большой тэтой?

Question

Я смотрю на следующую проблему:
T(n)=57*T(n/4) + O(n^3)
Я понимаю, что мне нужно использовать основную теорему, чтобы решить эту проблему, но все примеры в моем учебнике и в Интернете содержат большую тэту в уравнениивместо биг-о. Три случая одинаковы для обоих? Любая помощь очень ценится.

Answer 1

Вы правы. Это не одно и то же:

T(n) = 57*T(n/4) + O(n^3)
T(n) = 57*T(n/4) + \Theta(n^3)

Тем не менее, вы можете использовать основную теорему, чтобы получить некоторый big-O анализ для T(n). Следовательно, используя второй случай для анализа T(n), и используя O вместо Theta в конечном результате, как будто f(n) = Theta(g(n)), вы также можете сказать f(n) = O(g(n))!

Answer 2

Тета достаточно хороша для вашей цели: