Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #11194
| Path | csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!cs.uu.nl!news.stack.nl!.POSTED!not-for-mail |
|---|---|
| From | Willem <willem@toad.stack.nl> |
| Newsgroups | comp.lang.c, comp.lang.c++ |
| Subject | Re: Big O |
| Date | Wed, 2 Nov 2011 11:16:49 +0000 (UTC) |
| Organization | Stack Usenet News Service |
| Lines | 26 |
| Message-ID | <slrnjb29l1.3020.willem@toad.stack.nl> (permalink) |
| References | <j8r6fg$ih7$1@dont-email.me> |
| NNTP-Posting-Host | toad.stack.nl |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=us-ascii |
| Content-Transfer-Encoding | 7bit |
| X-Trace | mud.stack.nl 1320232609 9503 2001:610:1108:5010::135 (2 Nov 2011 11:16:49 GMT) |
| X-Complaints-To | abuse@stack.nl |
| NNTP-Posting-Date | Wed, 2 Nov 2011 11:16:49 +0000 (UTC) |
| User-Agent | slrn/0.9.9p1 (FreeBSD) |
| Xref | x330-a1.tempe.blueboxinc.net comp.lang.c:12522 comp.lang.c++:11194 |
Cross-posted to 2 groups.
Show key headers only | 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.
)
) 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
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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