# predicting runtime of $\mathcal{O}(n \log(n))$ algorithm, one “input size to runtime” pair is given

I'm given the runtimes for input size $n=100$ of some polynomial-time (big-Oh) algorithms and an $\mathcal{O}(n \log(n))$ one. I want to calculate the runtimes for: $200$, $1000$ and $10000$.

For the polynomials it is trivial. The results I should get for the $n \log n$ case are: $0.06$, $1$ and $20$ seconds respectively, where $0.03s$ was given for $n=100$.

I have tried: (examples should have $0.06$ as solution)

(1) $\frac{f(2x)}{f(x)}$ similarly to how I've got the right solution to the polynomials, $\frac{2x \log(2x)}{x \log x} = \ldots= 2 \log((2x)^{1/\log x})$, not getting anywhere, and substituting $n=100$ gives $2.3010$ for any $\log$ base.

(2) calculating the "unit time of execution" $x$, from $100 x \log(100x)=0.03$ after approximating the inverse of $y=n \log n$ for $y=0.03$, $n=1.03$ for natural $\log$, substitution gives: $1.48$. $n=1.02058$ for binary $\log$, substitution gives: $2.10$

(3) calculating "unit time of execution" from the polynomial cases, which yield different for each, and result in negative runtimes predictions for the nlogn algorithm

(?) I also thought of searching for a function that is $\mathcal{O}(n \log n)$ and fits onto the points given by the solution, but thats over my head.

How to get to the solution ? Did any of my attempts made sense ?

-
Thanks for the detailed answer. It probably just trying to emphasize the orders of growth, because it is a first assignment about computational complexity and big-Oh. But not knowing how the answer for that one case came along keeps bugging me, and I can't step over it for days now. Because it is a free online course, I can't just ask the TA. Do you think that one column of the solution is simply wrong ? (section assignment 5, last problem from see.stanford.edu/see/materials/icspacs106b/assignments.aspx) –  nlognfan Dec 22 '11 at 20:05
(I think this was supposed to be a comment to my answer, rather than a separate answer). Based on this new information, I'm quite certain that the solution set is simply wrong. I can see no justification for the numbers they give, much less any reason why a student would be expected to arrive at those numbers in particular. Next time please add such links to the source of the problem to the question itself; that makes it much easier to figure out which kind of answer would be useful. –  Henning Makholm Dec 22 '11 at 21:14
@nlognfan: your accounts have been merged. Please register your account to avoid creating duplicate accounts in the future. –  Qiaochu Yuan Dec 23 '11 at 2:04

Assuming this is a homework exercise, I think you're making it much more complex than it is.

You're being asked (implicitly) to imagine that an input size of $100$ is enough that all run-time contributions of terms that grow slower than $n\log n$ -- such as time for the program to start up, the $O(n)$ time it takes to read the input, and so forth -- are insignificant compared to the $n\log n$ term. (This is not an unproblematic assumption -- see below -- but that may not be what the question asks you to philosophize about).

In other words, suppose you can ignore everything else. Then the running time is $f(n) = Cn\log n$ for some constant $C$. Given that $f(100)=0.03$, you can find $C$ simply by plugging in $100$ to get $$C\cdot 100\log(100) = 0.03 \quad\text{ and therefore }\quad C = \frac{0.03}{200}=0.00015$$ Now you just use that $C$ to find $f(10000)=0.00015\times 10000\times 4=6$. But that is not the result you're expecting to get -- why would you expect $f(10000)$ to be $20$?

It's not a result of using a base-10 logarithm, because any other logarithm would just show up as a multiplicative factor in $C$ that is canceled out when we plug in concrete numbers later.

You certainly shouldn't expect $f(100)=0.03$ and $f(200)=0.06$, because that amounts only to a linear scaling of the runtime with no logarithmic factor at all. (It's possible to get this behavior with a constant term, of course, but then your problem is underspecified).

So perhaps it's not homework? Are the known good values ones you have measured in practice? In that case it is very likely that what you see is just due to measuring uncertainty -- $0.03$ seconds is a very short time to time a program, and you really have no business trying to extrapolate that by a factor of 100. How precise are your measurements even for such short intervals?

For example, a problem of size 100 will likely stay within the L1 cache whereas for a size of 10000 you begin to pay a price in cache misses that simply doesn't show up at all in the $n=100$ measurement.

Remember that big-O notation is about how the resource usage grows when $n$ is very large, and a nice big-O analysis can hide any amount of shenanigans and erratic behavior for small $n$, as long as there is some size above which the complexity behaves as the big-O notation claims. There's no guarantee about how large this threshold may be; even 10000 may be too small a problem size to see the big-O complexity in action.

-