CODEWITHSUNDEEP
algorithmcomplexity-theory
Léo Léopold Hertz 준영
Léo Léopold Hertz 준영

Reputation: 141340

Unable to deduce a table about algorithms' effectiveness

I am not completely sure about the following table

alt text http://files.getdropbox.com/u/175564/algTranslation.png

The table provides the size of problem that can be solved in the time limit given in the left-hand column when the algorithmic complexity is of the given size.

I am interested in the deduction of the table.

The table suggests me that

I am not sure how the values in the column of O(n * log(n)) have been deduced.

  1. How can you deduce the value 0.5M for O(n * log(n)) or 3000 for O(n^2)?

Upvotes: 0

Views: 294

Answers (3)

Antti Huima
Antti Huima

Reputation: 25542

if you can do 10,000,000 ops per second, then when you set n = 500,000 and calculate n * log(n) = 500,000 * log2(500,000) = 500,000 * 18 = 9,000,000 ops which is roughly 10,000,000 for the purposes of the "seconds" classification.

Similarly, with n = 3,000 you get n^2 = 9,000,000. So on every line the number of operations is roughly the same.

Upvotes: 1

Juha Syrjälä
Juha Syrjälä

Reputation: 34281

I think that this table gives simply some very approximate illustration how big n can be for different kind of complexities when you have fixed time (1 second, 1 minute, 1 hour, 1 day or 1 year) at your disposal.

For example O(n^3):

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

As you can see, the number are very rough approximations. It seems that author has wanted to use nice round numbers to illustrate his point.

Upvotes: 1

Guffa
Guffa

Reputation: 700670

No, n is not the number of seconds, it's the number of items to process.

O(n) means that the time to process the items is linear to the number of items.

O(n²) means that the time to proess the items is relative to the square of the number of items. If you double the number of items, the processing time will be four times longer.

See: Big O notation

The table assumes that there is a fixed amount of work per item, although the big O notation only specifies how an algorithm reacts to a change in number of items, it doesn't tell you anything about how much work there is per item.

Edit:
The values along the x axis of the table are just approximations based on the assumption that the work per item is the same. For example the value 3000 for O(n²) is rounded from the square root of 10 millions, which is ~3162.28. The cubic root of 10 millions is not 200, it's ~215.44.

In a real situatuon, two algorithms rarely do the same amount of work per item. An algorithm with O(log n) typically does more work per item than an O(n) algorithm for the same purpose, but it's still preferrable in most situations because it scales a lot better.

Upvotes: 4

Related Questions