Вычислите сложность процесса для следующей функции

Question

Как рассчитать сложность процесса для следующей функции?

int Compute (int n) 
{ 
    int j = 0; 
    int i = 0; 
    while (i<=n) 
    { 
     i = 2*j + i + 1; 
     j++; 
    } 
    return j-1; 
} 

Теперь я знаю, что цикл имеет O (N) времени сложность, но в этом случае i растет гораздо более быстрыми темпами. Принимая эту итерацию по итерации, я выяснил, что для каждой m-й итерации i = m^2. Но я все еще смущен, как рассчитать Big-O.

Answer 1

Если вы посмотрите на значения I и J в течение нескольких итераций:

i=1 
j=1 

i=4 
j=2 

i=9 
j=3 

i=16 
j=4 

и так далее. По математической индукции можно доказать, что я принимает квадратные значения: (2*n + n^2 + 1 = (n+1)^2)

Поскольку мы петля только тогда, когда я < = п и так как я принимаю Вейлы 1, 2^2, 3^2, ..., к^2 < = n, это означает, что мы останавливаемся, когда i = k переходит на sqrt (n). Следовательно, сложность представляется O (k), что означает O (sqrt (n)).