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

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