I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time.
I was wondering how to find the running time of an algorithm given the time complexity of it.
For example: An algorithm runs in $O(n \lg n)$ time and solves a problem of size 1000 in 23 seconds. It would solve a problem of 10000 in slightly over...
Or, for another example, a comparison between two:
- Suppose you have a computer that requires 1 minute to solve problem instances of size n = 100. What instance sizes can be run in 1 minute if you buy a new computer that runs 100 times faster than the old one, assuming the following Time complexities $T(n)$ for the algorithm?
(a) $O(n^2)$
(b) $O (2^n)$
Thanks, I'm a bit baffled.
$\endgroup$ 33 Answers
$\begingroup$One must make several assumptions to answer your question precisely. But making all the simplest assumptions, one has:
$k\ n \log{n} = 23$
and hence
$k \approx 3.3\ 10^{-3}$.
Then $k 10000 \log{10000} = 307$ second.
As for assumptions... note that a function that is in the class ${\cal O}(n^2)$ is also in ${\cal O}(n^3)$; conversely, some functions in ${\cal O}(n^3)$ are in ${\cal O}(n^2)$. For instance the function $g(n) = 1$ is in all of them! It is conceivable that your specific function is of constant time (which is in ${\cal O}(n\ \log{n}$)). So to answer your question you might assume that the bound is tight.
The proper way to pose such a problem would be to use the $\Theta (\cdot)$ notation, for asymptotically tight bound.
$\endgroup$ $\begingroup$You cannot know the exact time of a given order, but let me reformulate your question to be, what is the upper bound a given order for a given value of $N$.
For example,
If $N = 100$, what is the Upper bound time of $O(N^2)$?
We know that
$O(N^2) < O(N Log(N))$
Then an upper bound of $O(N^2)$ with $N = 100$ is $100 \log(100) = 100\cdot 6.64 = 664$
Now depending on the speed of the computer, you can determine how much time this will take.
You can do a simple application that makes 664 iterations, then calculate the time it takes.
$\endgroup$ $\begingroup$Despite the caveats you have gotten, the intended answer goes something like this. For the second part, if you can do $n=100$ of an $n^2$ algorithm on the old machine, you can do something like $100^2=10000$ operations in a minute. The new machine will do $100$ times this, which is $1,000,000$. We now need to find the $m$ such that $m^2=1,000,000$ and we find $m=1000$ Having a machine $100$ times as fast makes it so we can run $10$ times bigger a problem. If you can do $n=100$ of a $2^n$ algorithm, you can do $2^{100}=1267650600228229401496703205376$ operations in a minute. Due to the laws of exponents, if you multiply this by $100$ and ask what $2^m$ gives that result, it will be a fixed amount $\log_2 100 \approx 6.6$ higher, so you can do $m=106$ in a minute. A faster machine doesn't help much with an exponential algorithm.
$\endgroup$
