Unable to deduce a table about algorithms' effectiveness

Answer 1

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.

Answer 2

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.

Answer 3

Hi,

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.