Notices
Results 1 to 3 of 3

Thread: Big Oh Notation

  1. #1 Big Oh Notation 
    New Member
    Join Date
    Oct 2006
    Posts
    3
    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


    Reply With Quote  
     

  2.  
     

  3. #2 Re: Big Oh Notation 
    Guest
    Quote 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)



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






    Quote 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


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Dec 2006
    Posts
    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.
    Reply With Quote  
     

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
  •