# 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$$

The same idea can be applied to the second algorithm.

• thank you! can I check how you would do log to the base 2 of N please
– user652734
Mar 12, 2019 at 14:09
• 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. Mar 13, 2019 at 9:48
• right ok can I be a pain and ask you to show me with the numbers the L2 bit is throwing me off
– user652734
Mar 13, 2019 at 12:04
• Look, here you have a calculator that does it for you. The log function has a an option to select base 2-logarithms (lg2) Mar 13, 2019 at 13:44
• Can’t lie my mind is frazzled now 😂
– user652734
Mar 14, 2019 at 21:05