Определение большой (O) эффективности конкретной петли

Question

Меня спрашивают определить большую нотацию O для этого цикла.

int x = 1; 
    int n = 1000; 
    while (x < (n*n)) 
    { 
     int y = n; 
     while (y > 0) 
     { 
      y = y-1; 
     } 
     x = x+x; 
    } 

Теперь я вижу, что это вложенный цикл. Но это определенно не N^2, правильно? Я понимаю, что делает что-то O (n) или O (log (n)), но как я буду определять определение для определенного цикла, такого как этот?

Answer 1

Внутренний цикл проходит от п к , так что О (п).

Внешний контур

while (x < (n*n)) { 
    ... 
    x = 2*x; 
} 

логарифмическая, работает с к N * N, который был бы O (журнал (п)) = O (2 лог-н) = O (log n).

Поскольку петли вложенными, вы умножаете сложности получить O (п § п).