# How to count the biggest size of the problem during some time period?

We assume that time of solving the problem $$=f(n)\mu$$s. Now we have to calculate how big problem we can calculate for each time periods.

So there are: $$\lg n, \sqrt{n}, n, n\lg n, n^2, n^3, 2^n, n!$$,

How to calculate size of the biggest problem during those times periods?: 1s, 1min, 1h, 1 day, 1 month , 1 year, 100 years

I completely don't know how to start.

• by $\mu s$ you mean micro seconds? is $f(n)$ some proper complexity function?
– lox
Commented Apr 7, 2019 at 19:11
• For each pair of $f(n)$ and $t$ where $t$ is time, you have a formula: $t = f(n) \cdot \mu s$. Now you can do basic algebra and solve for $n$.
– ryan
Commented Apr 8, 2019 at 16:19

Freeman,

the answer is somewhat easy and you can do it with a simple calculator. I will assume that $$\mu s$$ represents a microsecond, i.e., 0.000001 second.

Let's take for example the calculus for $$n^2$$. You need to answer which value of $$n$$ makes $$0.000001 f(n^2) = time\_limit$$. Thus, we have:

$$0.000001 f(n^2) = 1 ~~~~~~~~\rightarrow n = 1000 ~~~~~~~~\text{(1 second)}$$
$$0.000001 f(n^2) = 60 ~~~~~~\rightarrow n = 7,745.97~\text{(1 minute)}$$
$$0.000001 f(n^2) = 3600 ~~\rightarrow n = 60,000 ~~~~\text{(1 hour)}$$
$$0.000001 f(n^2) = 72000 \rightarrow n = 268,328 ~~\text{(1 day)}$$

You need to compute that for all combinations of time limit and growth factor.
Try writing a simple computer program to compute such numbers and plot all of them like the figure below. Hope you go well on your studies :)