Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!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:26:02 +0000 (UTC)
Organization: Stack Usenet News Service
Lines: 45
Message-ID: <slrnjb2a6a.3020.willem@toad.stack.nl>
References: <j8r6fg$ih7$1@dont-email.me> <j8r7m7$p1g$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 1320233162 9503 2001:610:1108:5010::135 (2 Nov 2011 11:26:02 GMT)
X-Complaints-To: abuse@stack.nl
NNTP-Posting-Date: Wed, 2 Nov 2011 11:26:02 +0000 (UTC)
User-Agent: slrn/0.9.9p1 (FreeBSD)
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:12523 comp.lang.c++:11195

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