4

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 :)

David Undy
  • 943
  • 2
  • 7
  • 12
  • 1
    It might be helpful to check ["Big O, how do you calculate/approximate it?"](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Camilo Martinez Jun 07 '13 at 14:48

3 Answers3

7

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).

Taylor Brandstetter
  • 3,523
  • 15
  • 24
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))

jemmanuel
  • 466
  • 4
  • 13
  • 1
    `for(i = n/2; i < n; i++)` iterates `O(n)` times, not `O(n^2)`. I also don't see what that example has to do with the question. As for your first code snippet being `O(n^2)`: that's true, but I think you'd need to explain *why* it's `O(n^2)` for the answer to be truly helpful. – sepp2k Jun 07 '13 at 15:00
  • @sepp2k : fixed errors. thnx for pointing out. I was just promoting the use of Big-O notation while calculating some complex nested loops...thought it would help – jemmanuel Jun 07 '13 at 15:08
1

A precise and formal way to find out the number of iterations of your algorithm:

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32