2

Possible Duplicate:
Plain English explanation of Big O

Dear all,

As I read information about some algorithms, occasionally, I encounter algorithm performance information, such as: O(1), O(n), O(n^2) etc..

Could I kindly get explanation on how to translate and understand this performance data? What kind of O(n) variants are available, and what do they mean in practice?

Thank you.

Community
  • 1
  • 1
Bunkai.Satori
  • 4,698
  • 13
  • 49
  • 77
  • 2
    Wikipedia is your friend here. It has an excellent article on this. http://en.wikipedia.org/wiki/Big_O_notation – Michael Dorgan Jan 23 '11 at 20:14
  • possible duplicate of (among others) [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) –  Jan 23 '11 at 20:15
  • Thanks, I am already reading Wikipedia. Best regards. – Bunkai.Satori Jan 23 '11 at 20:24

2 Answers2

9

You need an explanation of big-O notation.

It is a measure of the complexity of an algorithm. As N tends to infinity, the direction the amount of time will take.

One thing you need to be aware of is that O(N) multiplied by a constant is still O(N). There is no such thing really as O(2N).

O(1) means something takes a constant time, i.e. the amount of time it takes is unrelated to the amount of data you are processing.

O(N) means it is proportional to the amount of data you are processing, so if it takes a minute to process a million records, it will take 2 minutes to process 2 million.

O(N^2) means it is proportional to the square of N. 1000 records takes a minute, 2000 takes 4 minutes, 4000 takes 16 minutes, etc.

You can also have O(log N) and O(N log N). You can use any base for log but one commonly measures in log base 2. So a million records would measure as 20 because 2^20 is close to a million, and 2 million records would be 21. For N log N, a thousand records would be equivalent to 10,000 because the log of 1000 is approximately 10. 2 thousand records would be 22,000, as the log of 2000 is approximately 11.

CashCow
  • 30,981
  • 5
  • 61
  • 92
  • Thank you CashCow for your answer. I will check Wikipedia for Big-O notation too. – Bunkai.Satori Jan 23 '11 at 20:21
  • @Bunkai: This is good, but not *quite* right. O(1) does not mean taking constant time. It means there's a constant upper bound on the time - a certain amount of time it will not take more than, no matter what. It's always allowed to take less. Same idea for others. – Mike Dunlavey Jan 23 '11 at 22:29
  • @Bunkai: Another way to think of it: Draw that curve: 1, N, N^2, logN or NlogN. Which curve will your running time fit under for all N, given that you're allowed to divide the running time by any constant you like? – Mike Dunlavey Jan 23 '11 at 22:40
  • Note that the log can be to any base simply because changing the base is the same as multiplying by a constant. – Chris Hopman Jan 23 '11 at 23:37
  • One also has to understand that adding a constant doesn't change the complexity so it can be that adding more records doesn't increase as much as you think and for a small amount of data in particular a higher complexity algorithm can be faster than a low complexity one. e.g. using linear search in 4 records can be faster than binary search. – CashCow Apr 29 '15 at 10:22
1

Start with Wikipedia: http://en.wikipedia.org/wiki/Big-o_notation.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680