Как оценивать алгоритмы с циклами сейчас должно быть понятно. А что делать с рекурсивными алгоритмами?

Для начала напишите рекуррентную формулу для функции сложности C(n). В данном случае, она будет выглядеть так:

\displaystyle C(n) = 1 + C(n-1)

1 — тратится на if. А С(n-1) — сложность рекурсивного вызова.

Дальше можно раскрыть рекурсию до конца, превратив формулу в ряд.

\displaystyle C(n) = 1 + 1 + 1 + ... + 1 = n = \Theta(n)

А ряд — это то, с чем мы уже работали при оценке циклических алгоритмов. Иногда ряд оказывается тривиальным — как в этом случае. Иногда это арифметическая или геометрическая прогрессия. В совсем сложных случаях окажется какой-то сложный, неизвестный ряд, и придется вспоминать математический анализ. Впрочем, сложный ряд можно встретить и в алгоритме с циклами.

Поупражняйтесь на следующем примере.

1. Какая сложность у F1? 1 балл