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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Condition
AI Thread Summary
The discussion revolves around determining the value of n for two algorithm cost functions: f(n) = n log n and f(n) = n!. The main question is to find n such that n log n equals 10^6 microseconds. The equation x ln x = 10^6 is identified as a key equation, with an approximate solution of x around 87847.5. It is noted that this equation does not have solutions in elementary functions for non-zero a, suggesting the need for approximation methods like binary search to find n. Additionally, the conversation highlights the relevance of big-O notation in algorithm complexity, indicating that for n = 10^4, n log n is less than 10^6, while for n = 10^5, it exceeds 10^6. The participants express understanding and appreciation for the insights shared.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Last edited:
Technology news on Phys.org
evinda said:
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$
 
chisigma said:
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)
 
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$.
 
Evgeny.Makarov said:
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)
 
Thread 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
Back
Top