Что такое Большой О этого псевдокода?

Question

x <--1
for i <--0 to n do
    k <-- i
   while k> 0 do
         x <-- x*2
         k <-- k-1
return x

Это O (n)? Цикл while увеличивает сложность?

Answer 1

Когда i = 0, внутренний цикл работает 0 время
Когда i = 1, внутренний цикл работает 1 время
Когда i = 2, внутренний цикл работает 2 раз
Когда i = 3, внутренний цикл выполняется 3 раз
...
Когда i = n, внутренний цикл запускается n раз
Сложив все это: 0+1+2+3+...+n = n*(n+1)/2
Таким образом, сложность времениO(n^2)

Answer 2

Я согласен с Xashru выше. O (N ^ 2) * * +1001