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

Groups > comp.programming > #3741

Re: algorithm analysis Big-O

Show all headers | View raw

In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>,
Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:
> 
> > 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.
> 
> With that meaning, neither O(1) < O(n) nor O(n) < O(1) would be true, so
> if that is what was meant, it's not very useful.  The problem here is
> that if f is O(1) it is also O(n).

Indeed.  What was I thinking ....  (*WAS* I thinking .... )  


> That there is some confusion here is not surprising.  The exact meaning
> of operators near a "big O" is often hard to determine.  For example,
> some people write "g = O(f)", but whatever the "=" means, it certainly
> isn't equality.  In other fields you'll see it "added":
> 
>   p(x) = x^5 + a.x^4 + O(x^2).
> 
> Again, that can't be normal addition.
> 
> One approach to formalising it is to say that O(f) is the set of all
> functions, g, that have the property that |g(n)| < C.f(n) for some
> constant C and all but a finite set of n.  (There are other ways to get
> similar meanings -- there doesn't seem to be a universal definition.)
> 
> With this definition, O(f) is a real "thing" (just a set) and we can use
> normal set operations on it.  For example, where many people write,
> informally, "g = O(f)", we can now write "g in O(f)" using set
> membership.  With this more formal definition, using less than
> (especially in ASCII) as the subset relation is not unreasonable.  With
> this meaning, O(n) < O(n^2) because all functions that are in O(n) are
> also in O(n^2), whilst there are functions in O(n^2) that are not in
> O(n).  (I'd use a Unicode "subset of" if that were not likely to derail
> the thread with a discussion of non-ASCII postings.)
> 
> I like this approach, but it's not universal and it may even be a
> minority view.  Some authors just think of O(f) as a shorthand for a
> property (pronounced "order of f") and, if they are careful, they write
> "g is O(f)".  If they are not so careful and write "g = O(f)" the "=" is
> meant to be pronounced "is".  In this sort of informal context, I'd
> guess that O(f) < O(g) means that all functions that are O(f) are also
> O(g), and that there exists at least one function that is O(g) that is
> not O(f).  However, this is derived from what I *want* it to mean,
> rather than any guess at what the OP meant.
> 
> In complexity theory there are lots of sets of things with interesting
> properties (decidable languages, P, NP and so on), so I think it makes
> perfect sense to formalise O(f) as just another set of things with some
> interesting property.
> 

"Couldn't snip a word" ?

Thanks -- this is pretty much the meaning I think I would have had
in mind if I'd been thinking clearly.  :-)??  I like your set-based
definition, but defining O(f(n)) as a property seems plausible too
(and then you could convey the "<" idea using implication?  i.e., if
a function has property O(f(n) it also has property O(g(n))?).


-- 
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