Codesnippet с runtime t (n) ∈ Θ (n^3/2)

Question

Я пытаюсь решить упражнение, где мне нужно написать код с помощью (n) ∈ Θ (n^3/2) времени исполнения ,

Мне разрешено использовать рекурсии, сложение, вычитание, деление целых чисел на 2, для циклов, если операторы, <,>, ==, а также if- и return-statements.

Чтобы получить время выполнения t (n) ∈ Θ (n^3), мне нужно будет просто использовать 3 for-loops, также я думаю, что было это правило, где с помощью if-statement время выполнения логарифмическая. У меня нет идеи о том, как получить время выполнения t (n) ∈ Θ (n^3/2).

Я был бы очень рад, если бы кто-нибудь мог дать вам совет. Спасибо :)

Answer 1

Вот фрагмент кода, чтобы найти дивизоры факторы всех чисел от 2 до N сделано в O (N^3/2).

for(int i=2;i<=N;i++) 
    { 
     for(j=2;j*j<=i;j++) 
     { 
      if(i%j==0) 
      { 
       printf("another non-trivial divisor pair for %d is %d,%d",i,j,i/j); 
      } 
     } 
    } 

Внешний контур является O (N) и внутренняя является O (N^1/2).