Нужно объяснение для анализа сложности времени итерационной программы

Question

Какова временная сложность следующей итерационной программы?

void function(int n) {
    int count = 0; 
    for (int i=0; i<n; i++) 
        for (int j=i; j< i*i; j++) 
            if (j%i == 0) 
            { 
                for (int k=0; k<j; k++) 
                    printf("*"); 
            } 
}

Answer 1

(n * n * n ^ 2) создание сложности для трех циклов - O (n ^ 4).

Когда i = 5,

Это подразумевает общую сложность,

for (int j=5; j< 25; j++)  
     if (j%i == 0) // runs O(i) times
     {
      // runs j times when j = 5, 10, 15, 20
            for (int k=0; k<j; k++) {
                printf("*"); // runs j times when j =  5(1 + 2 + 3+ 4)
               // runs  j times which is i*i*(i*(i-1)/2) times
               // runs i^4 times
            }
     }

это означает, что общая сложность равна O (n ^ 4).Помните, что нотация big-O используется для определения верхней границы времени выполнения фрагмента кода, поэтому говорят, что время выполнения равно O (n5), если время выполнения фактически равно O (n4), а ненеправильно;это просто не туго.