Re: Big oh Notation

From: Stewart Gordon (smjg_1998_at_yahoo.com)
Date: 02/27/04 

Date: Fri, 27 Feb 2004 17:34:37 +0000

Oskar Sigvardsson wrote:

> I learned about Big-Oh from Concrete Mathematics by Graham, Knuth,
> Patashnik, excellent book. And also Donald Knuths monumental (well,
> three volumes so far) The Art Of Computer Programming.
>
> And by the way, I'm almost positve that QS is of order O(n log n).

In the average case, yes. It's O(n^2) worst case, O(n) best case.

> (And even if it isn't most people would write it O(n log n) anyway
> because
>
> O(n log 2n) = O(n(log 2 + log n)) = O(n log n + n log 2) = O(n log n)

Either something is O(n log n) or it isn't. O(n log 2n) is indeed
identical to O(n log n). An order is an order, not the way some
convention chooses to write it down.

Stewart. 

-- 
My e-mail is valid but not my primary mailbox, aside from its being the 
unfortunate victim of intensive mail-bombing at the moment.  Please keep 
replies on the 'group where everyone may benefit.

Relevant Pages

  • Re: Big oh Notation
    ... I learned about Big-Oh from Concrete Mathematics by Graham, Knuth, ... Patashnik, excellent book. ... three volumes so far) The Art Of Computer Programming. ...
    (comp.lang.java)
  • Re: Periodicity of a^n mod c
    ... I have requested The Art of Computer Programming, Volume 2, Seminumerical ... Algorithms, from a nearby branch of my jursdiction's public library, for pickup ... at my local branch. ...
    (sci.math)
  • Re: Towards a Formula for Primes
    ... Niven has written a couple of good books ... on irrationality. ... I was reading "The Art of Computer Programming" by ...
    (sci.math)
  • Donald Knuth to speak at the Computer History Museum
    ... A Dozen Precursors of Fortran ... Donald Knuth is perhaps best known for having written the classic, ... In The Art of Computer Programming, ...
    (comp.lang.fortran)
  • Re: Hansen chains do not always produce optimum addition chains
    ... > In The Art of Computer Programming, Third Edition, Vol. 2, 4.6.3, ... Guy has a long bibliography. ...
    (sci.math)