0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ thank you! can I check how you would do log to the base 2 of N please $\endgroup$
    – user652734
    Mar 12, 2019 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$ Mar 13, 2019 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$
    – user652734
    Mar 13, 2019 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$ Mar 13, 2019 at 13:44
  • $\begingroup$ Can’t lie my mind is frazzled now 😂 $\endgroup$
    – user652734
    Mar 14, 2019 at 21:05

You must log in to answer this question.