Вычислить время выполнения алгоритма и записать результат используя асимптотическую нотацию

Рассчитайте время выполнения алгоритма (псевдокод приведен ниже). Запишите результат асимптотической нотацией. Объясните каждый шаг

Автор решения: Harry

Если все работает строго как написано, без оптимизаций, то мы получаем

Согласно основной теореме (см. Кормен и др., Алгоритмы, построение и анализ, 3 изд., стр. 120), поскольку a = 4, b = 2 и

то

Вот и всё.

→ Ссылка