Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Re: Big O (http://www.velocityreviews.com/forums/t805437-re-big-o.html)

 BartC 11-02-2011 10:56 AM

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

 Willem 11-02-2011 11:26 AM

Re: Big O

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

 BartC 11-02-2011 11:39 AM

Re: Big O

> 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

 gwowen 11-02-2011 04:08 PM

Re: Big O

On 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

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:13 PM.