Как оценить относительную эффективность алгоритмов с учетом времени выполнения как функции от 'n'?

Question

Рассмотрим два алгоритма, A и B. Оба алгоритма решают одну и ту же проблему и имеют временную сложность. (с точки зрения количества элементарных операций, которые они выполняют) с учетом соответственно на

а) (n) = 9n+6

б) (n) = 2(n^2)+1

(i) Какой алгоритм является лучшим асимптотически?

(ii) Что является лучшим для небольших входных размеров n, и для каких значений n это дело? (При необходимости вы можете предположить, что n> 0.)

Я думаю, что это А. Я прав?

А каков ответ на часть B? Что именно они хотят?

Answer 1

Асимптотически, a (n) лучше, поскольку оно O (n) , а не O (n ² ) . Вот график времени работы как функция n . Как видите, a (n) медленнее только для небольших значений n .