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

Groups > comp.lang.c > #12516 > unrolled thread

Big O

Back to article view | Back to comp.lang.c

Contents

  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

#12516 — Big O

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?

[toc] | [next] | [standalone]

#12518

"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?

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

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#12523

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


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

[toc] | [prev] | [next] | [standalone]

#12526

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

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

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#12536

"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

[toc] | [prev] | [next] | [standalone]

#12539

On Nov 2, 2:28 pm, "Scott Fluhrer" <sfluh...@ix.netcom.com> 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.

[toc] | [prev] | [next] | [standalone]

#12521

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);

[toc] | [prev] | [next] | [standalone]

#12522

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?

Google for "Euler's gamma", and/or "Harmonic number".


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

[toc] | [prev] | [next] | [standalone]

#12530

Willem wrote:

> Google for "Euler's gamma", and/or "Harmonic number".

e.g. http://en.wikipedia.org/wiki/Harmonic_number

[toc] | [prev] | [next] | [standalone]

#12532

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web