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,327
    Rep Power
    8

    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
    14,043
    Blog Entries
    7
    Rep Power
    23

    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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Help with postfix expression
    By javajavajava in forum New To Java
    Replies: 3
    Last Post: 11-12-2010, 12:11 PM
  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, 08: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
  •