Вопрос по оценке сложности алгоритма?

Question

[Chemodan228]

Ребят почему в строке, где находится i-ое число Фибоначчи временная сложность равна O(n)?
Заранее спасибо.

Answer 1

[Wataru]

Видимо, тут считается сколько раз эта строка выполнится суммарно, а не сколько она сама занимает.
Т.к. эта строка в цикле, который повторяется O(n) раз, то и строка эта (которая выполняется за константное время) всего займет O(n).