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

Groups > comp.programming > #3729

Re: algorithm analysis Big-O

Show all headers | View raw

On Sat, 14 Sep 2013 06:32:23 -0700 (PDT), gdotone@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? 
>
>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? 
>
>what about: 
>      for ( int i=0: i<1000: i++) 
>      { 
>          int a = a + i; 
>          int t = t + i; 
>      } 
>are we only concerned of the number of item or will the two assignment 
>statement change the analysis in some way? 
>
>what about: 
>
>       for (int i =0; i <1000; i++) 
>       { 
>           for ( int t =1; i < 1000; i++) 
>           { 
>               int a = a+i+t; 
>           } 
>        } 
>
>is this O(n^2)? why? how do you come up with that? 


Actually both of those are O(1) - they run in constant time.

If, OTOH, you had:

  for(i=0; i<n; i++)
    {
    ...work...
    }

  for(i=0; i<n; i++)
    {
    for(j=0; j<n; j++)
      {
      ...work...
      }
   }

Those would be O(n) or O(n**2), respectively.

If the inner loop had a different quantity of items to process:

  for(i=0; i<n; i++)
    {
    for(j=0; j<m; j++)  /* note 'm' */
      {
      ...work...
      }
   }

it would usually be described as O(n*m).


>what are example of something being O(n/2), or O(log  n )?   


You'd never have O(n/2), the constant factor is always ignored.  IOW,
from a Big-Oh standpoint:

  for(i=0; i<n; i++)
    {
    ...a tiny bit of work...
    }

and:

  for(i=0; i<n; i++)
    {
    ...lots and lots and lots of work...
    }

Are both exactly O(n), even though the second would obviously have a
much longer runtime.

As for some of the other common classes, binary search is O(log n),
and Heapsort is O(n * (log n)).  Note that Quicksort, in the common
case, is also O(n log n), but is typically about twice as fast sorting
things as Heapsort is.

And usually only the "biggest" term counts.  So if you had:

  for(i=0; i<n; i++)
    {
    for(j=0; j<n; j++)
      {
      ...work...
      }
   }
  for(i=0; i<n; i++)
    {
    ...some other work...
    }

Which could be described as O(n**2 + n), that would usually just be
O(n**2).


>and how do you know that they are that? 


Conceptually you're just estimating how the work done by the algorithm
grows with the size(s) of the input.  You can even do that
empirically, just by running with a bunch of different sized inputs,
putting a counter into the middle of the algorithm, graphing the
results, and then picking a curve to fit.  Much more commonly we do it
analytically, by looking at known patterns (we know a loop is O(n), a
binary search is O(log n)), and nestings and combinations of those
things.  It can get quite tricky when there are dependencies between
the different bits - even something as simple as Shellsort doesn't
have a fully developed understanding of its runtime in the general
case (although for many choices of decrement, it does).

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