How can I find the n,that satisfies this condition?

[evinda]

Hello! (Wave)

I am looking at the following exercise:

Suppose that we have an algorithm,which cost is $f(n) \ \mu sec (10^{-6} sec)$.

If $f(n)=n \log{n}$,to what should $n$ be equal,so that the cost is $10^6 \ \mu sec$?

So,it must be:

$$n \log{n}=10^6 \Rightarrow n^n=10^{10^6}$$

But how can I find the $n$,that satisfies this condition? (Thinking)

Also,how can I find the $n$,such that $f(n)=n!=10^6 \mu sec$? (Thinking)

 

[chisigma]

Hello! (Wave)

I am looking at the following exercise:

Suppose that we have an algorithm,which cost is $f(n) \ \mu sec (10^{-6} sec)$.

If $f(n)=n \log{n}$,to what should $n$ be equal,so that the cost is $10^6 \ \mu sec$?

So,it must be:

$$n \log{n}=10^6 \Rightarrow n^n=10^{10^6}$$

But how can I find the $n$,that satisfies this condition? (Thinking)

Also,how can I find the $n$,such that $f(n)=n!=10^6 \mu sec$? (Thinking)

The equation $\displaystyle x\ \ln x = 10^{6}$ has solution $x \sim 87847.5$...

Kind regards

$\chi$ $\sigma$

 

[evinda]

The equation $\displaystyle x\ \ln x = 10^{6}$ has solution $x \sim 87847.5$...

Kind regards

$\chi$ $\sigma$

So,can we just find an approximation? (Thinking)

 

[Evgeny.Makarov]

According to WolframAlpha, the equation $x\log(x)=a$ does not have a solution in elementary functions when $a\ne0$. So yes, you should find an approximation, for example, using binary search (establishing an interval that contains a solution and dividing it in half repeatedly). It seems that this problem comes from computer science, where complexity of algorithms is measured not even up to the order of magnitude, but up to a multiplicative constant (big-O notation). So it may be sufficient to say that if the logarithm is to the base 2, then $n\log n<10^6$ for $n=10^4$, but $n\log n>10^6$ for $n=10^5$.

 

[evinda]

According to WolframAlpha, the equation $x\log(x)=a$ does not have a solution in elementary functions when $a\ne0$. So yes, you should find an approximation, for example, using binary search (establishing an interval that contains a solution and dividing it in half repeatedly). It seems that this problem comes from computer science, where complexity of algorithms is measured not even up to the order of magnitude, but up to a multiplicative constant (big-O notation). So it may be sufficient to say that if the logarithm is to the base 2, then $n\log n<10^6$ for $n=10^4$, but $n\log n>10^6$ for $n=10^5$.

Nice,I understand..thank you very much! (Smile)