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?

$\endgroup$
  • 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 '18 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 '18 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 '18 at 12:53
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).

$\endgroup$
  • 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 '18 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 '18 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 '18 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 '18 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 '18 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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