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

Groups > comp.programming > #3739

Re: algorithm analysis Big-O

Show all headers | View raw

In article <O90Zt.29906$sr1.508@en-nntp-04.dc1.easynews.com>,
Richard Damon  <Richard@Damon-Family.org> wrote:
> On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
> > O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
> >  
> 
> Only for n large.


Isn't that part of the def ....  Oh.  Well, maybe not exactly:
The formal definition of what it means for a function to be O(f(n))
does include a notion of "for sufficiently large n", but I'm not
finding, in a quick Web search, a formal definition of what 
"O(f(n)) < O(g(n))" means.  But I'm inclined to think that it's
something along the lines of "if function f1(n) is O(f(n)), and
function g1(n) is O(g(n)), then for sufficiently large n,
f1(n) < g1(n)".  Maybe someone who knows this off the top of
his/her head, or has the right books nearby, can fill in the
details.


> It is quite possible for a O(2^n) algorithm to be much faster than a
> O(log n) algorithm for small n, primarily because the purpose of the O()
> notation is to look at scaling at large values of n.


But this part I agree with!


> When determining the O() value for an algorithm, you look at how much of
> something (time, memory, or what ever) the algorithm uses as n
> increases. At some point, the amount of that stuff that an O(x(n))
> algorithm uses will be approximately k*x(n) for all n sufficiently
> large. We ignore the k factor, as that becomes a function of the units
> we are using, and as long as k is "reasonable" it doesn't normally
> affect our decisions as to which algorithm to use. There can be cases
> though, where n doesn't really get extremely large, where the the scale
> factor may make a "larger" O() be better than the lower O(), or you need
> to look at "smaller" growth terms as they have a significant scale
> factor and there contribution isn't negligible.


To the OP:  I don't have a specific book or other resource to recommend,
but a search term that may be useful is "analysis of algorithms".  


-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

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