Re: Big O

From	Gen <g@g.com>
Newsgroups	comp.lang.c, comp.lang.c++
Subject	Re: Big O
Date	2011-11-02 18:43 +0530
Organization	A noiseless patient Spider
Message-ID	<j8rflf$9ts$1@dont-email.me> (permalink)
References	<j8r6fg$ih7$1@dont-email.me>

Cross-posted to 2 groups.

Show all headers | View raw

On 02-11-2011 04:06 PM, Gen wrote:
> 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.
>
> Can someone help me analyze this?

Thank you all. That was very helpful.

Back to comp.lang.c++ | Previous | Next — Previous 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 Gen <g@g.com> - 2011-11-02 18:43 +0530

csiph-web