Амортизированная стоимость Runtime для алгоритма, чередующегося между O (n^2) & O (n^4)

Question

Если я реализую алгоритм, который работает на O(n^4) с текущим временным временем, а затем O(n^2) на следующем.

• - сложность по-прежнему max[O(n^4), O(n^2)]?
• Есть ли способ получить полином в диапазоне [2, 4) для сложности? Я что-то вроде O(n^2.83) в среднем
• Как рассчитать среднюю стоимость времени выполнения, амортизированную с t=0...inf? Это всего лишь [O(n^2) + O(n^4)]/2?

Answer 1

О (п) незначительна над О (п) так как частное от деления первого на второй имеет нулевой предел при п возрастает до бесконечности.

Так что ваш алгоритм просто O (п)

Читать на Big 0 notation вики страницы и любые хорошие учебники о пределах многочленов.