Velocity Reviews > C++ > Re: Big O

# Re: Big O

BartC
Guest
Posts: n/a

 11-02-2011

"Gen" <(E-Mail Removed)> wrote in message news:j8r6fg\$ih7\$(E-Mail Removed)...
> 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

Willem
Guest
Posts: n/a

 11-02-2011
BartC wrote:
)
)
) "Gen" <(E-Mail Removed)> wrote in message news:j8r6fg\$ih7\$(E-Mail Removed)...
)> 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

BartC
Guest
Posts: n/a

 11-02-2011

"Willem" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> BartC wrote:
> )
> )
> ) "Gen" <(E-Mail Removed)> wrote in message news:j8r6fg\$ih7\$(E-Mail Removed)...
> )> 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

gwowen
Guest
Posts: n/a

 11-02-2011
On Nov 2, 2:28*pm, "Scott Fluhrer" <(E-Mail Removed)> 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

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.