Results 1 to 3 of 3
  1. #1
    borgan is offline Member
    Join Date
    Jan 2011
    Posts
    1
    Rep Power
    0

    Default Big-oh expression help!

    I have two questions about big-oh expression.
    The first one is:

    for(i=1;i<n;++i)
    for(j=1;j<floor(i/2);j++)
    {
    ...statements that require exactly j operations...
    };
    For this one, i think that the number of operations written by big-oh operations is O(n^2)


    for (i=1;i<n;++i)
    {
    ...statements that require at most 10^9 /i operations
    }
    For this one, i do not understand the meaning of "at most 10^9 /i operations". Hope someone give me some suggestions. Thx.

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    If you are calculating for the worst case, then you assume the inner statement uses 10^9/i operations. It depends on wether you are calculating for best, average or worst case performance - generally you consider worst case since in some algorithms, its a deal breaker even if unlikely.

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by borgan View Post
    For this one, i think that the number of operations written by big-oh operations is O(n^2)


    for (i=1;i<n;++i)
    {
    ...statements that require at most 10^9 /i operations
    }
    For this one, i do not understand the meaning of "at most 10^9 /i operations". Hope someone give me some suggestions. Thx.
    That loop does M/1+M/2+M/3 ... +M/n operations where M == 10^9. 10^9 is a (large) constant so that loop does O(n) operations.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Help with postfix expression
    By javajavajava in forum New To Java
    Replies: 3
    Last Post: 11-12-2010, 11:11 AM
  2. Help with regular expression
    By mr.ab18 in forum New To Java
    Replies: 2
    Last Post: 08-06-2010, 10:01 PM
  3. JSF expression inside another JSF expression
    By barbarabxl in forum JavaServer Faces (JSF)
    Replies: 2
    Last Post: 05-21-2010, 03:03 PM
  4. regular expression
    By ras_pari in forum Advanced Java
    Replies: 27
    Last Post: 10-07-2009, 12:25 PM
  5. Quick reg. expression help
    By RR_QQ in forum New To Java
    Replies: 4
    Last Post: 02-10-2009, 07:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •