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 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top