Квадратичное уравнение в обозначении Big-Oh

Question

Я готовлюсь к промежуточному тесту относительно времени выполнения Big-Oh. Один из вопросов, с которыми я сталкиваюсь, состоит в следующем повторении, и вопрос состоит в том, чтобы задать нотацию Биг-О.

T (n) = 2T (n / 2) + (2n ^ 2 + 3n +5)

Итак, используя основную теорему, где k> log_b (a), в этом вопросе я думаю, что k равно 2 из (2n ^ 2), a равно 2 от 2T и b равно 2 от (n / 2). Следовательно, время выполнения основной теоремы - это когда k> log_b (a), то есть 2> log_2 (2) = 1, тогда T (n) = O (n ^ 2).

Правильно ли мое мышление? Я никогда не видел квадратичного времени выполнения внутри T (n), но я вполне уверен, что в этом вопросе это O (n ^ 2).

Спасибо за ваш вклад!

Answer 1

Да, O (n ^ 2) правильно. На самом деле подобный пример есть в статье Википедии о главной теореме . Эта функция может быть любой, и в основном вы просто сравниваете глубину и ширину дерева рекурсии со стоимостью этой дополнительной функции и проверяете, что доминирует в сложности.