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:
- $N^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.