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