Mail Archives: djgpp/1998/01/23/17:30:25
>Gili wrote:
>>
>> Hi,
>>
>> I have noticed that lots algorithms provide their efficency as
>> O(n), where N is the number of elements they are operating on. The
>> last math course I have taken is Calculus 2 and I do not recall ever
>> seeing the O(n) function. What does it mean? How efficient is
>> something with O(n)? Thanks in advanced,
>>
>> Gili
I know this is off-topic, but I'm going to answer the question anyway. In a
mathematical sense, something that is O(f), where f is some function, does not
increase as fast as f as n->infinity. It is 'asymptotically dominated' by f, or
stays less than f. For an algorithm, say a sorting algorithm, it's basically
the number of comparisons to sort n things.
So an O(n) algorithm is better than O(n log n) or O(n^2). (This may be
confusing if you see things about Taylor series where O(n^2) or O(n^3) are
taken to be negligible because they're very small - in that case they're
proportional to a power of a number with abs. value less than 1, so they are
very small.)
For more about O, o, asymptotic dominance, etc. look for a discrete math book.
- Raw text -