0
$\begingroup$

In CLRS, there's a question in the first chapter that says for certain functions $run time = f(n)$, to calculate the max number of $n$ given the run time. The math works out simply. For example, for $f(n) = \sqrt{n}$ microseconds, given a 1 second run time there is ${\frac{1\ second}{10^{-6}\ seconds}}^2$ inputs $n$, which I got from $\sqrt{n}\ microseconds = 1\ second$ and solving for n.

My confusion comes from trying to make a proportion for the system like I would for a dimensional analysis problem. I have $\frac{\sqrt{n}\ microseconds}{n\ inputs}$ and the other fraction is $\frac{1\ second}{x\ inputs}$. Here when I solve for $x$ I get $10^6*\sqrt{n}$. I think my dimensions don't make sense somehow, but in my head, saying 'it takes square root of n microseconds for n inputs' comes out as $\frac{\sqrt{n}\ microseconds}{n\ inputs}$.

Thank you!!

$\endgroup$
1
  • $\begingroup$ In algorithms, this is usually done in [big O notation] (rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation ) and it related to number of computations needed. Take for example grade school long multiplication it's $O(n^2)$ meaning as n grows larger, it takes roughly $n^2$ (because there's not enough of a factor for additions to gain a factor of n to become $n^3$) steps, for two n digit numbers, each multiply should take roughly the same amount of time, on a given hardware. $\endgroup$
    – user451844
    Commented Jul 27, 2017 at 1:04

1 Answer 1

Reset to default
0
$\begingroup$

Since no one really answered this, this is what I think is some physical intuition behind the situation.

It takes $\sqrt{n}\ microseconds$ to solve a given problem, so no matter what it is true that it took $\frac{\sqrt{n}\ microseconds}{problem\ of\ any\ size\ n}$. So if the problem took 1 second to solve (for whatever n), the fraction would be $\frac{1\ seconds}{problem\ of\ size\ n}$. And since we know the first fraction is always true we can set up a proportion $\frac{\sqrt{n}\ microseconds}{problem\ of\ any\ size\ n} = \frac{1\ seconds}{problem\ of\ size\ n}$. So now we can solve the proportion for $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .