discrete math-Complexity of algorithms The best and worst case time complexity of an algorithm we
are using is O(n \log_2 n) For an input of size n = 1000$ the algorithm
ran in 25 seconds. Approximately how long should the algorithm run for input size n = 4000?
For reference, this is how I though it'd be done.
The running time of O(n log2 n) is directly proportional to n log2 n. i.e., T(n log2 n) = cn log2 n For n =1000, the running time is 1000 log2 1000, which is given as 25 secs. i.e., the running time when input size n = 1000 is 9965.78 (approx.). Thus, for n = 4000, the running time is 4000 log2 4000, which runs approximately 100 secs.
 A: You forgot the constants in the $O(\cdot)$ [*]. (Edit: that is, before you edited your question. As of the current version, you do take them properly into account.)
A more correct (but still not actually correct, see [*]) way to do so would be to estimate the constant with the $n=1000$ case, first assuming the asymptotics behavior is already a good approximation for $n\geq 1000$.
I.e., assume the running time $T(n)$ satisfies roughly $T(n) \simeq cn\log_2 n$ for some constant $c>0$, for $n \geq 1000$. Then, you first need to find $c$, by writing
$25 \simeq T(1000) = c\cdot 1000 \log_2 1000$ -- so that $c\simeq \frac{25}{1000 \log_2 1000}$.
Then, you plug $c$ back to compute (an approximation of) $T(4000)$:
$$
T(4000) \simeq c\cdot 4000\log_2 4000
$$

[*] actually, because of this the whole problem does not make sense, as the asymptotics may only "kick in" for, e.g. $n \geq 10^{78}$. For instance, $n\log_2 n + 90^{147}$ is $O(n\log_2 n)$, but the first term is negligible for $n \ll 90^{147}$ or so.
Another reason is that this is the worst case complexity, but we use one observed running time on one instance to estimate the constant $c$. Even without the problem due to asymptotics outlined above, a typical instance of size $n$ may not follow the worst-case time complexity. There are many algorithms that have a worst-case running time of, say, $O(n^2)$, but take much less time on a "typical", average-case instance (e.g., $O(n)$).
