"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1u9ig9nnen59q$.ajozwlsekr7l.dlg@40tude.net...
> On Thu, 21 Jun 2012 04:50:34 -0700 (PDT), Austin Obyrne wrote:
>
>> 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.
>
>> This is surprising to me - is it right?
>
> Yes, O(nX)=O(Y) for all n>0.
>
> O(f)=O(g) when lim f/g exists, finite, non-zero.
>
> http://en.wikipedia.org/wiki/Big_O_notation

Or, if you want a directly relevant reference, see A.18(3-4/2) in Ada 2005 
or Ada 2012.

http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p3

(I'm sure the wikipedia article is less terse, but I wanted to point out 
that this is defined in the Ada Standard as well as common programming 
analysis.)

                          Randy.