Big O

So this problem came from a discussion with some friends that went on for 3 days. Although this looks like a simple big O analysis it was quite deceiving for me (and apparently for everyone else) when I first saw it and went from guessing it was O(N^8), then guessing again O(N^6) to finally O(N^4) with some real analysis.
This is a typical case when your brain wants to make things worse than they are.

The problem is: What is the big O of a piece of code like this given than array.length is O(N)?

for i… N array.length
—>for j… N array.length
——>for k… N array.length

My approach was to imagine it first for the case we usually know, when array.length is O(1).
If you think of it graphically, the first two loops can be seen as a 2D matrix. Every i,j in the matrix represents the big O of one step.
Then if we “zoom in” into any of those steps, we see that every “1″ unrolls into a O(N) operation because of the third loop. So in total we come up with O(N^3).

for i… N array.length
—>for j… N array.length
——>for k… N array.length

_________N_____

   j0   j1  j2  j3  j4
i0 1   1   1   1   1
i1 1   1   1   1   1 ...    |
i2 1   1   1   1   1        N
i3 1   1   1   1   1        |
i4 1   1   1   1   1                    <--O(N*N ) = O(N^2)
            |
           /\  (exploding a step)
          /  \
              _
      k0 1    |                         <--O(N)
      k1 1    N
      k2 1    |
      k3 1                           So O(N * N^2) = O(N^3)

Now I imagined it for the case of our problem, when array.length takes O(N). In the i,j matrix every step now is not “1″ but “2N+1″ because it includes 2 array.length (one for the i loop and another for the j loop). Then if we “zoom in” into any of those steps, we see that every “2N+1″ becomes “2N+N^2″ since the third loop is now O(N^2). So the total of the i,j matrix is O(N^4).

for i… N array.length
—>for j… N array.length
——>for k… N array.length

________________N______

      j0       j1         j2
i0 ( 2N+1)  ( 2N+1)   ( 2N+1)
i1 ( 2N+1)  ( 2N+1)   ( 2N+1)         |
i2 ( 2N+1)  ( 2N+1)   ( 2N+1)         N
i3 ( 2N+1)  ( 2N+1)   ( 2N+1)         |
i4 ( 2N+1)  ( 2N+1)   ( 2N+1)       <-- O((2N+1)*(N)) = O(N^2)
                  |
                 /\   (exploding a step)
                /  \  

            k0 1+N   |              <--  O(N*(N+1)) = O(N^2)
            k1 1+N   N
            k2 1+N   |
            k3 1+N                

                                        So O(N^2 * N^2) = O(N^4)

Advertisement