2
$\begingroup$

Table with time intervals along the top, from one second to one century, and various functions of n down the side

I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $\lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?

Improve this question
$\endgroup$
3
  • 16
    $\begingroup$ This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be. $\endgroup$
    – user92772
    Aug 27, 2018 at 13:36
  • $\begingroup$ As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents. $\endgroup$
    – JiK
    Aug 28, 2018 at 10:56
  • $\begingroup$ @JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)\leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column. $\endgroup$
    – David Richerby
    Aug 28, 2018 at 12:53

1 Answer 1

Reset to default
37
$\begingroup$

The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.

i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.

One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.

For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).

Improve this answer
$\endgroup$
12
  • 10
    $\begingroup$ Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers. $\endgroup$
    – Raphael ♦
    Aug 27, 2018 at 10:15
  • 7
    $\begingroup$ Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592\cdot 10^9$ characters of input! In fact it only consumed $259198\cdot 10^7$ characters. $\endgroup$
    – leftaroundabout
    Aug 27, 2018 at 14:46
  • 6
    $\begingroup$ @Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)). $\endgroup$
    – gnasher729
    Aug 27, 2018 at 15:25
  • 6
    $\begingroup$ @leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize. $\endgroup$
    – gnasher729
    Aug 27, 2018 at 15:27
  • 1
    $\begingroup$ According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$ $\endgroup$
    – SamYonnou
    Aug 27, 2018 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.