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

Groups > comp.programming > #3723

Re: algorithm analysis Big-O

Show all headers | View raw

On Saturday, September 14, 2013 2:32:23 PM UTC+1, gdo...@gmail.com wrote:
> O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
> my question has to do with actually determining that Big-O type. 
>
> Questions: 
>  
> n represents the number of data items? 
> 
Normally, yes. N is the size of the problem, which is generally the number
of data items in a list that the algorithm operates on. But occasionally, e.g.
factorisation algorithms, N is an integer.
> 
> 
> given a loop: 
> 
>        for (int i =0; i<1000: i++) 
>        { 
>           int a = a + i; 
>        } 
> 
> this would be a O(n), because as the number of items increases the time 
> to run increase linearly? 
> 
the loop for(i=0;i<N;i++) is O(N), even if the loop body is empty.

the nested loops

for(i=0;i<N;i++)
  for(ii=0;ii<N;ii++)
  
are O(N^2)

and so on. They're doing N and N*N or N squared operations, even if they
are just increments and comparisons.
>
> Can you recommend a book or several books that discuss algorithm analysis,
>  with plenty of examples?
> 
Big(O) notation is quite simple once you get the hang of it. The hard part
is devising algorithms with lower big(O) representations than the naive or
strightforwards approaches.
Big(O) also applies to memory use, by the way, or to anything that scales
with increasing N. 

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

Thread

algorithm analysis Big-O gdotone@gmail.com - 2013-09-14 06:32 -0700
  Re: algorithm analysis Big-O Johann Klammer <klammerj@NOSPAM.a1.net> - 2013-09-14 16:50 +0200
  Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-14 08:45 -0700
  Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-14 12:29 -0400
    Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-14 11:12 -0700
      Re: algorithm analysis Big-O Willem <willem@turtle.stack.nl> - 2013-09-14 19:21 +0000
        Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-14 23:12 -0400
          Re: algorithm analysis Big-O Willem <willem@turtle.stack.nl> - 2013-09-15 08:16 +0000
            Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-22 19:04 -0400
              Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-23 02:32 +0100
          Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-17 15:07 -0700
    Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 20:27 +0100
    Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-15 18:09 +0000
      Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 20:47 +0100
        Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-15 20:42 +0000
          Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-16 00:56 +0100
            Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-19 20:26 +0000
  Re: algorithm analysis Big-O Öö Tiib <ootiib@hot.ee> - 2013-09-14 11:08 -0700
  Re: algorithm analysis Big-O Robert Wessel <robertwessel2@yahoo.com> - 2013-09-14 13:43 -0500
  Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:01 +0100

csiph-web