Как оценивать алгоритмы с циклами сейчас должно быть понятно. А что делать с рекурсивными алгоритмами?
Для начала напишите рекуррентную формулу для функции сложности C(n). В данном случае, она будет выглядеть так:
1 — тратится на if. А С(n-1) — сложность рекурсивного вызова.
Дальше можно раскрыть рекурсию до конца, превратив формулу в ряд.
А ряд — это то, с чем мы уже работали при оценке циклических алгоритмов. Иногда ряд оказывается тривиальным — как в этом случае. Иногда это арифметическая или геометрическая прогрессия. В совсем сложных случаях окажется какой-то сложный, неизвестный ряд, и придется вспоминать математический анализ. Впрочем, сложный ряд можно встретить и в алгоритме с циклами.
Поупражняйтесь на следующем примере.
Войдите или зарегистрируйтесь, чтобы отвечать на тесты и решать задачи.