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

Groups > comp.programming > #3776

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

Show all headers | View raw

example from a textbook:
how can big O notation be used to estimate the sum
of the first n positive numbers?

solution:
 
1 + 2 + ... + n <= n + n + ... + n = n^2

From this inequality it follows that 
1+2+3+...+n = O(n^2) 
taking C = 1, k =1

my question  is the n^2 in  ... <= n + n+ ... + n = n^2

is it because n^2  grows at a greater rate than n + n + ...+ n
which to me would be constant times n : k(n)

i mean it could be said that 
1+2+ ...+ n is bigO(n^3)  

ok, so, one uses the lowest bigO function? by convention. right?
but, in this example that would not need be the case 
to show a bigO as O(n^3) would work too, right?

Back to comp.programming | Previous | Next — 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