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

Groups > comp.lang.c++ > #11193

Re: Big O

Cross-posted to 2 groups.

Show all headers | View raw

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.
>

If I understand correctly, the code will run

n + n/2 + n/3 + n/4 + ... + 1

times in total (I'm including the fractional parts, which won't make
any difference, asymptotically. If you want  to be precise, you can
put an upper/lower bound on using ceiling() and floor()).

This sum is the same n * (1 + 1/2 + 1/3 + 1/4 + ... 1/n), and the sum
of that harmonic series is log(n) + Euler's constant + a term that
decays like 1/(2n).  So the asymptotic runtime will be

n * log(n) + gamma*n + 1/2.

or, in Big-O its O(n log n);

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 Gen <g@g.com> - 2011-11-02 18:43 +0530

csiph-web