Re: Big O

Discussion in 'C Programming' started by BartC, Nov 2, 2011.

  1. BartC

    BartC Guest

    "Gen" <> wrote in message news:j8r6fg$ih7$...
    > I have program where the other loop runs 'n' times.
    > When i is 0 in the outer loop, the inner loop runs n times
    > When i is 1 in the outer loop, the inner loop runs n/2 times
    > When i is 2 in the other loop, the inner loop runs n/3 times.
    >
    > i.e. The inner loop runs n/(i+1) times.
    >
    > If I had express the complexity of this program in Big O notation,
    > what would it be?
    >
    > I am thinking it will be O(nlogn) - but I am not sure how to justify it
    > because it's not exactly a binary algorithm.


    If you take any of those examples, if you make n ten times as big, will it
    take ten times as long?

    In that case it sounds like O(n). What's the relationship between i and n?

    --
    Bartc
    BartC, Nov 2, 2011
    #1
    1. Advertising

  2. BartC

    Willem Guest

    BartC wrote:
    )
    )
    ) "Gen" <> wrote in message news:j8r6fg$ih7$...
    )> I have program where the other loop runs 'n' times.
    )> When i is 0 in the outer loop, the inner loop runs n times
    )> When i is 1 in the outer loop, the inner loop runs n/2 times
    )> When i is 2 in the other loop, the inner loop runs n/3 times.
    )>
    )> i.e. The inner loop runs n/(i+1) times.
    )>
    )> If I had express the complexity of this program in Big O notation,
    )> what would it be?
    )>
    )> I am thinking it will be O(nlogn) - but I am not sure how to justify it
    )> because it's not exactly a binary algorithm.
    )
    ) If you take any of those examples, if you make n ten times as big, will it
    ) take ten times as long?

    "any of those examples" ??? That's one single example.

    ) In that case it sounds like O(n). What's the relationship between i and n?

    You seem to be assuming that this is a very simple question.
    It is not.
    This is an example of the kind of loop he's talking about:

    for (i = 0; i < n; i++) {
    for (j = 0; j < (n/(i+1)); j++) {
    do_something();
    }
    }

    Given that there is no closed form for 1/1+1/2+1/3+...+1/(n-1)+1/n,
    it's not trivial to prove that this is O(n lg n).


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, Nov 2, 2011
    #2
    1. Advertising

  3. BartC

    BartC Guest

    "Willem" <> wrote in message
    news:...
    > BartC wrote:
    > )
    > )
    > ) "Gen" <> wrote in message news:j8r6fg$ih7$...
    > )> I have program where the other loop runs 'n' times.
    > )> When i is 0 in the outer loop, the inner loop runs n times
    > )> When i is 1 in the outer loop, the inner loop runs n/2 times
    > )> When i is 2 in the other loop, the inner loop runs n/3 times.
    > )>
    > )> i.e. The inner loop runs n/(i+1) times.
    > )>
    > )> If I had express the complexity of this program in Big O notation,
    > )> what would it be?
    > )>
    > )> I am thinking it will be O(nlogn) - but I am not sure how to justify it
    > )> because it's not exactly a binary algorithm.
    > )
    > ) If you take any of those examples, if you make n ten times as big, will
    > it
    > ) take ten times as long?
    >
    > "any of those examples" ??? That's one single example.


    OK, I thought it was a choice of i, not all of them added together.

    --
    Bartc
    BartC, Nov 2, 2011
    #3
  4. BartC

    gwowen Guest

    On Nov 2, 2:28 pm, "Scott Fluhrer" <> wrote:

    > It might not be trivial to prove from scratch, but it's a well known
    > mathematical fact that was in fact proven quite a while ago by Leonhard
    > Euler.


    Euler didn't give a closed form for the partial sum, but he did give
    an aymptote that more than suffices in this case. However, its quite
    easy to show that the partial sums harmonic series

    [Caution: Bad ASCII integral signs ahead]

    N N
    / dx / dx
    |----- + 1 < (1 + 1/2 + 1/3 + 1/N) < | ----- + 1
    / x+1 / x
    1 1

    which are sufficiently tight bounds for this problem.
    gwowen, Nov 2, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    11
    Views:
    706
    Roedy Green
    Sep 18, 2005
  2. Shaguf
    Replies:
    0
    Views:
    343
    Shaguf
    Dec 24, 2008
  3. Shaguf
    Replies:
    0
    Views:
    442
    Shaguf
    Dec 26, 2008
  4. Shaguf
    Replies:
    0
    Views:
    229
    Shaguf
    Dec 26, 2008
  5. Shaguf
    Replies:
    0
    Views:
    210
    Shaguf
    Dec 24, 2008
Loading...

Share This Page