Search code examples
algorithmmathbig-oasymptotic-complexity

What does 'log' represent in asymptotic notation?

I understand the principles of asymptotic notation, and I get what it means when something is O(1) or O(n2) for example. But what does O(log n) mean? or O(n log n) for example?

Solution

  • Check: en.wikipedia.org/wiki/Big_O_notation

    Remeber that log increases slowly than a an exponential function. So, if you have an algorithm that is n^2 and other, that doing the same, has a logarithmic function, the last would be more efficient (in general term, not always!).

    To evaluate the complexity of a function (or algorithm) you must take in consideration the execution in time and space, mainly. You can evaluate a function or algorithm with other parameters, but, initially, those two would be OK.

    EDIT: http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

    Also, check the sorting algorithms. Will give great insight about complexity.