MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: question on big-O-notation
  • Next by Date: Change the scale and draw grid
  • Previous by thread: question on big-O-notation
  • Next by thread: Re: question on big-O-notation