# how to work out a computer program running time

I have a question and im not sure how to tackle it.... algorithms have running times proportional to the following functions of the input size, denoted N:

1. $$N^2$$
2. $$2^N$$

In one minute of computing time, they can each successfully complete processing an input of size 1000. What size input can each successfully handle given one hour of computing time?

Well, for the first algorithm, the running time $$T$$ is said to be proportional to $$N^2$$. Mathematically, this can be expressed as $$T= T(N) = C N^2$$ where $$C$$ is an unknown constant. Applying our formula to the data given in the question we get $$T(1000) = 1000^2 C = 10^6C = 1$$ since the time is one minute. Solving for $$C$$, we get $$C = 10^{-6}$$. Now, to find the size of the problem one can afford in one hour we just need to use the formula again: $$T(N) = 10^{-6} N^2 = 60$$ since one hour lasts sixty minutes. Solving for $$N$$ we obtain $$N = \sqrt{60 * 10^{6}} \approx 7746$$
• Any calculator will give you the natural logarithm ($\log$) of a number $x$. You can use that and the fact that for any logarithmic function $L(a^b) = b L(a)$ to calculate the logarithm in base 2 of N: $2^{L_2(x)} = \mathrm{e}^{\log(x)}$; and then taking the log of both sides gives the relation $L_2(x) \log(2) = \log(x)$, which you can use. – Guillermo BCN Mar 13 at 9:48