Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #12536

Re: Big O

Cross-posted to 2 groups.

Show all headers | View raw

"Willem" <willem@toad.stack.nl> wrote in message 
news:slrnjb2a6a.3020.willem@toad.stack.nl...
> BartC wrote:
> )
> )
> ) "Gen" <g@g.com> wrote in message news:j8r6fg$ih7$1@dont-email.me...
> )> 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).

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.  gwowen gave a good summary elsethread.

-- 
poncho

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Big O Gen <g@g.com> - 2011-11-02 16:06 +0530
  Re: Big O "BartC" <bc@freeuk.com> - 2011-11-02 10:56 +0000
    Re: Big O Willem <willem@toad.stack.nl> - 2011-11-02 11:26 +0000
      Re: Big O "BartC" <bc@freeuk.com> - 2011-11-02 11:39 +0000
      Re: Big O "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-11-02 10:28 -0400
        Re: Big O gwowen <gwowen@gmail.com> - 2011-11-02 09:08 -0700
  Re: Big O gwowen <gwowen@gmail.com> - 2011-11-02 04:15 -0700
  Re: Big O Willem <willem@toad.stack.nl> - 2011-11-02 11:16 +0000
    Re: Big O Noob <root@127.0.0.1> - 2011-11-02 13:23 +0100
  Re: Big O Gen <g@g.com> - 2011-11-02 18:43 +0530

csiph-web