Trouble Finding Big O Time for this loop

Question

I'm trying to find the Big O running time 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 would be O(n^3) because of the 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 Arithmetic Series), so it's actually O(n^4).

Answer 2

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

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

in your sample code let i := 1 -> p where p = O(n^2) then since the code runs in O(p^2) its running time will be O(n^4)

Using the Big-O notation can help you through 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 it as constantly dividing n by 2 : definition of log]
so the total running time is : O(n(logn))