Calculating Running Time (in seconds) of algorithms of a given complexity

Question

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:

2. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.