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

2.

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

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

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement