- **C Programming**
(*http://www.velocityreviews.com/forums/f42-c-programming.html*)

- - **Re: Big O**
(*http://www.velocityreviews.com/forums/t805437-re-big-o.html*)

Re: Big O"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 |

Re: Big OBartC 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 |

Re: Big O"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 |

Re: Big OOn 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. |

All times are GMT. The time now is 05:16 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.