Re: question on big-O-notation
- To: mathgroup at smc.vnet.net
- Subject: [mg41601] Re: [mg41564] question on big-O-notation
- From: David Terr <dterr at wolfram.com>
- Date: Wed, 28 May 2003 04:57:31 -0400 (EDT)
- References: <200305270547.BAA00471@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Alan Tang wrote:
>Hello:
>
>Is it correct?
>
>for (i=0; i<1000000; i++)
>{
> for (j=10; j<n; j++)
> {
> a[j]=a[j]+i;
> }
>
>}
>
>big-O-notation equation
>(1000001) + 10000000 * [(1+n-10) * (n-10)]
>
>Thanks!
>
>
>--
>
>Best Regards,
>Alan Tang
>
>
I don't understand your question, but what you've written does not
appear to be correct. Your program computes the sum of the nonnegative
integers up to 1000000, which is equal to 500000500000. In general, the
sum of the first nonnegative integers up to n is equal to n(n+1)/2,
which is equal to O(n^2), using the big-O notation. I hope this answers
your question! By the way, you wouldn't want to use the above program
since it's much easier to simply compute n(n+1)/2.
David
- References:
- question on big-O-notation
- From: Alan Tang <atang@netband.com.hk>
- question on big-O-notation