Thread: Big Oh Notation

I have the following VB code:

____

For k = 1 To 4*n Step 2
iSum = iSum +1
Next k
For i = 1 To 2*n
For j = 1 To 3*n Step 3
iSum = iSum +1
Next j
iSum = iSum + 1
For m = 1 To 2*n
iSum = iSum + 1
iSum = iSum + 1
Next m
Next i


____

What is the complexity of this code in terms of Big Oh notation? I'm getting confused on what to look at. Is the notation going to be:
O(n^2)?
O(n^4)?

Why?

Thanks

Originally Posted by Kilace

I have the following VB code:

____

For k = 1 To 4*n Step 2
iSum = iSum +1
Next k

In viz bas could simply be written as...

isum=isum+ (n*2)

Originally Posted by Kilace

For i = 1 To 2*n
For j = 1 To 3*n Step 3
iSum = iSum +1
Next j

iSum = iSum + 1

For m = 1 To 2*n
iSum = iSum + 1
iSum = iSum + 1
Next m
Next i

again in vis baz:

for i = 1 to 2*n
isum= isum+n+1
isum=isum +(4*n)
next i

which itself can be shortened again...

Now whatever big oh is, try again (I've never heard of it)

Originally Posted by Kilace

____

What is the complexity of this code in terms of Big Oh notation? I'm getting confused on what to look at. Is the notation going to be:
O(n^2)?
O(n^4)?

Why?

Thanks

I'm not that familiar with VB, so please forgive me...

For k = 1 To 4*n Step 2
iSum = iSum +1
Next k

this would be n, because the number of interations grow in proportion to n times some constant, c1

For i = 1 To 2*n
For j = 1 To 3*n Step 3
iSum = iSum +1
Next j
iSum = iSum + 1
For m = 1 To 2*n
iSum = iSum + 1
iSum = iSum + 1
Next m
Next i

one outer loop whose interations are proportional to n times some constant c2, with two inner loops whose interations are proportional to n times some constants c3 and c4. The presense of the 2*n or 3*n may change the constants of c, but the exact value of c is not relevant to calculating the big oh (if I recall..)

so, that ends up being:

c1*n+c2*n(c3*n+c4*n) = c1*n+c2*c3*n^2+c2*c4*n^2

which, as far as big oh is concerned is = n + n^2 = O(n^2)

so, I think the the big oh is n^2.

you'd get O(n^4) if the loops were nested four loops deep, which I'm not seeing the the VB. I could be wrong, c++ is my native language afterall.

anyone feel free to correct me if i'm wrong.