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 ?
 A: 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.
A: I believe the problem (as reported here) is underspecified.
Recall the definition: $$f \in O(g) \textrm{ exactly when } \exists x_0, c > 0 \colon \forall x > x_0 \colon |f(x)| \leq cg(x)$$
Consider now some function $f$ and a family $h_k$ for $k \in \mathbb{N}$, defined such that $h_k(x) = f(x)$ on the finite list of input-output pairs you are given, and $h_k(x) = f(x)/k$ for all other $x$.
If $f \in O(n \log n)$ then $h_k \in O(n \log n)$ for all $k > 0$.
Are you being asked to evaluate $h_1$ or $h_2$ or something else? If all you have is a finite list of input-output pairs and the fact that $g \in O(n \log n)$ where $g$ is the function you must evaluate, you don't have enough information since $g$ could be $h_k$ for any $k > 0$.
Requiring $g$ to be increasing won't save the question: instead, set $h_k(x) = f(x)$ on all $x$ up to and including the largest given input $x_m$, and $h_k(x) = f(x_m) + \frac{k}{k+1} (f(x_m) - f(x))$ whenever $x > x_m$. Note that $h_k$ is continuous for all $k$ if $f$ is so adding that requirement won't fix the question either.
The fundamental problem is that $O(\cdot)$ describes the behavior of functions asymptotically, and the description is too loose to compute specific values. If you are given that $g(x) \leq ax + b$ for some $a$ and $b$ and for all $x$, how would you find $g(200)$? You have no lower bound, and you only know that some upper bound exists but you don't know what $a$ and $b$ are. I guess your inputs constrain them but not enough (e.g. choose $b$ bigger than your largest output, then $a$ can be anything).
Side note, to motivate the above question: if $f$ is either monotonic or continuous and $g$ is either monotonic or continuous, and uh I think $g$ has to be eventually bounded below by a positive constant and their domains have to have a lower bound (e.g. 0), then $f \in O(g)$ is true exactly if there exists $a, b$ such that for all $x$ we have $f(x) \leq ag(x) + b$. (In one direction, let $a = c$ and let $b$ be the largest value $f$ takes before $x_0$. In the other, let $x_0$ be such that $g(x) > d > 0$ when $x > x_0$ and do algebra.)
