0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ by $\mu s$ you mean micro seconds? is $f(n)$ some proper complexity function? $\endgroup$ – lox Apr 7 '19 at 19:11
  • $\begingroup$ 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$. $\endgroup$ – ryan Apr 8 '19 at 16:19
0
$\begingroup$

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 :)

Plot of big-o notations P.S.: This figure was retrieved from here.

$\endgroup$

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.