Re: My Invention of "Bug Sort".

[Austin Obyrne <austin.obyrne@hotmail.com>]

On Thursday, June 21, 2012 8:23:12 AM UTC+1, Manuel Collado wrote:
> El 21/06/2012 7:13, Simon Wright escribió:
> > "Jeffrey R. Carter"<ggsub@pragmada.co.cc>  writes:
> >
> >>> 2 ) In "O(N log N)" do I assume log to the base 'e' or what.
> >>
> >> In "Big-O" notation, log is understood to be to the base 2.
> >
> > Isn't there a constant factor between log2(x) and ln(x)? Which is taken
> > up in the O?
> >
> >     N = e**x = 2**y
> >
> > Taking natural logs,
> >
> >     ln N = x = y.ln 2
> 
> Yes. In "Big-O" notation, the base for log() is irrelevant.
> 
>    O(log N) = O(ln N)
> 
> Both expressions denote exactly the same set of functions.
> 
> -- 
> Manuel Collado - http://lml.ls.fi.upm.es/~mcollado

---------------


This is surprising to me - is it right?

<<Yes. In "Big-O" notation, the base for log() is irrelevant. 

   << O(log N) = O(ln N) 

<< Both expressions denote exactly the same set of functions. 

In general,

A change of base in logarithms:

Log(base(a)M = Log (base(b))M / Log (base(b))'a'.

Applying that,In particular here,

Ln of N = Log2N / Ln 2


Unless it is true that there is some constant incorporated in O that verifies this, then

N(Ln N) /=  N(Log2 N)

Which is it?

On face value it appears totally incorrect arithmetically, I'm surprised that such an anomaly would be acceptable. 

Austin O'Byrne