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

Groups > comp.programming > #3751

Re: algorithm analysis Big-O

Show all headers | View raw

In article <0.8be74675a3c51fd4b4c6.20130916005604BST.87d2o9tzaj.fsf@bsb.me.uk>,
Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:
> 
> > In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>,
> > Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> <snip>
> >> 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.
> <snip>
> >> ... Some authors just think of O(f) as a shorthand for a
> >> property
> <snip>
> > ...  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))?).
> 
> Yes, though the zealot in me (see below) leans toward using <= for the
> meaning of that implication.
> 
> The distinction between a set and the property that defines membership
> is not one that would bother many mathematicians.  In fact, notation is
> often successful when it forms a kind of mathematical metaphor, rather
> than encapsulating an exact meaning.  Look how dy/dx displaced f-with-a-
> dot-over-it, probably because of what the division suggests despite
> being, formally, meaningless.  You can even pretend that dy/dx really is
> a fraction and still get the right answer in some circumstances.  I
> think there's a lot of that kind of thing going on with the various ways
> in which O(f) is used.


I'm not sure I completely understand what you're getting at here, but
if you want to say that "<=" means different things in different contexts
(sometimes numeric inequality, sometimes some other kind of ordering,
possibly a partial ordering), and that it's best to be clear what it
means in a given context -- yes, I agree.


> There's a great book about what mathematics really is called The
> Mathematical Experience by Davis and Hersh.  In one chapter, they review
> the more than 2000 years of presenting the Chinese remainder theorem.
> One example is "in the hands of a contemporary computer scientist":
> 
>   If n = p1^a1.p2^a2...pr^ar is the decomposition of the integer n into
>   distinct prime powers: pi^a1 = qi, then the cyclic group Zn has the
>   product representation
> 
>        Zn ~= Zq1 x Zq2 x ... x Zqr.
> 
> They then make a remark that has stayed with me for decades:
> 
>   "... it is true that computer science in its theoretical formulation
>   is dominated by a spirit of abstraction which defers to no other
>   branch of mathematics in its zealotry."
> 
> Though it can be seen as a little snide, I like to think of it as both a
> warning and a commendation.  Though I am no theoretical computer
> scientist I do have "tendencies" which I try to keep in check by
> bearing this remark in in mind.
> 


The authors have a more math-positive view of computer science than at
least one practicioner, then.  (Though how nice if they are right!)
A favorite quote of mine (not because I necessarily agree, but 
because -- I'm not sure I can articulate why!)

"Computer scientists are more willing to explore unconventional
proof styles. Unfortunately, I have found that few of them
care whether they have published incorrect results. They often
seem glad that an error was not caught by the referees, since that
would have meant one fewer publication. I fear that few computer
scientists will be motivated to use a proof style that is
likely to reveal their mistakes. Structured proofs are unlikely
to be widely used in computer science until publishing incorrect
results is considered embarrassing rather than normal."

-- ``How to Write a Proof,'' Leslie Lamport,
	DEC SRC Research Report 94, February 14, 1993.

On the other side, maybe, there's Edsger Dijkstra, who, if I remember
right, in one of his books explains the somewhat unconventional proof
style *he* uses, in a way that seems to connote that he knows how to
present proofs better than mathematicians.  I think it's in the same
section where he says something about punctuation that has the same
connotation about experts in that field.  Well, he was well-known
for having strong and sometimes unconventional opinions.  :-)?
And in both cases IIRC he did have a point!

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