Какова временная сложность следования за рядами Фибоначчи

Question

Я не понял, как это O (n ^ 2) ... на изображении, прикрепленном в соответствии со мной, должно быть O (n)

array[n];
array[0] = 1;
array[1] = 1;
for i = 2 to i = n:
   array[i] = array[i-1] + array[i-2]
return array[n]

Answer 1

Ссылка неверна. Каждая итерация этого l oop требует времени O (1) для выполнения, и она выполняется O (n) раз, поэтому стоимость этого l oop равна O (n). Похоже, что слайд случайно умножил общую стоимость O (n) l oop на количество итераций O (n), чтобы неправильно получить член O (n ² ).

Ваш анализ верен - этот код выполняется за время O (n).