Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3779

Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc..

Show all headers | View raw

On Tuesday, September 24, 2013 7:19:32 AM UTC-4, Ben Bacarisse wrote:
> gdotone@gmail.com writes:
> 
> 1 + 2 + ... + n <= n + n + ... + n 
>
>It means that the n n's on the right must be 
>less than or equal to (equal only when n=1) to the n numbers on the 
>left.  The sum on the right is, exactly, n^2, hence the "= n^2" at the 
>end.  Having found an upper bound, you can write it using big O. 

Ah, ok. 

n+n+n =3(n)
so,
n+n+...+n =n(n) = n^2 ?

>Not really by convention, no.  Generally you pick the bound that is the 
>most useful, and that is almost never one that is too generous. 
>Sometimes you write a bound that you know is too generous, simply 
>because you can't prove a tighter one. 

ok

>Up until the O(..) gets written there's 
>nothing in the argument about "growing faster" or any such notion.

ok

i think i see. i'll try several problems.

thanks, 

g.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. gdotone@gmail.com - 2013-09-23 23:55 -0700
  Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. Öö Tiib <ootiib@hot.ee> - 2013-09-24 02:11 -0700
  Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-24 12:19 +0100
    Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. gdotone@gmail.com - 2013-09-24 07:21 -0700
      Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-24 15:58 +0100
        Re: big O example, i found a few textbooks, CLR 3rd, Mark A. Weiss, etc.. gdotone@gmail.com - 2013-09-24 08:10 -0700

csiph-web