Problems finding Big O Time for this cycle

Question

I am trying to find the Big O runtime for the following code snippet:

for( i = 0; i < n * n; i++ ) for( j = 0; j < i; j++ ) k++; 

I'm not sure if it will be O (n ^ 3) due to multiplication of n or just O (n ^ 2). Some help would be appreciated :)

Answer 1

The inner loop will execute exactly 0 + 1 + ... + n ^ 2 - 2 + n ^ 2 - 1 = (n ^ 2) (n ^ 2 - 1) / 2 times (see the Arithmetic series ), therefore case O (n ^ 4).

Answer 2

for (i: = 1 → n) {for (j: = 1 → i) {something
}
}

works in O (n ^ 2) [the innermost cycle works 1,2,3 .... n times as the value of n increases, so in the end it runs for the sum 1 + 2 + 3 ... + n = O ( n ^ 2)]

in your code example, let i: = 1 → p, where p = O (n ^ 2) then, since the code works in O (p ^ 2), its run time will be O (n ^ 4)

Using Big-O notation can help you in some situations. Consider this:
for (i = n / 2; i <n; i ++) {for (j = 2; j <n; j = j * 2) {something
}
}

the outer loop runs O (n) , and the inner loop runs O (log (n)) [see its like constant dividing n by 2: log definition]
therefore total runtime: O (n (logn))

Answer 3

An exact and formal way to find out the number of iterations of your algorithm: