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

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:

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

• Since by definition the big $O$ is merely an upper bound, which only takes effect after some unknown, possibly extremely large n, and it's vague up to a constant factor, it's literally impossible to determine actual running time from it for any particular $n$. If you know it takes a minute for $n=1000000$, you still may not have reached the $n$ where the bound holds. Even if you have, without knowing the constant factor you have no idea how close to the upper bound you are....and even if you did, there's nothing that says it can't ever decrease for larger $n$. Commented Dec 6, 2015 at 2:05
• For the sake of the question, can't you just assume that it won't decrease? Commented Dec 6, 2015 at 2:20
• @GillDei Something that's $O(n^2)$ is also $O(2^n)$. If you know that it's $O(2^n)$ but not $O(n^2)$, then you know a lot more than simply that it's $O(2^n)$. Commented Dec 6, 2015 at 2:22

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.

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.

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.