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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.