patternMinor
n log n = c. What are some good approximations of this?
Viewed 0 times
thisapproximationswhatlogaresomegood
Problem
I am currently looking into Big O notation and computational complexity.
Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic complexities grow with the size of the input.
The question asks:
For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.
The time periods are 1 second, 1 minute, 1 hour, 1 day, 1 month, 1 year, 1 century.
The functions $f(n)$ are seemingly common time complexities that arise in algorithms frequently, the list being:
$$ \log_2n, \quad \sqrt{n}, \quad n, \quad n \log_2 n, \quad n^2, \quad n^3, \quad 2^n \quad \text{and} \quad n!$$
Most are fairly straightforward algebraic manipulations. I am struggling with two of these, and both for the same reason:
If $c$ is the time in microseconds, the two I am struggling with are
$$ n \log_2 n = c$$
$$ n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$$
For $n!$ I thought of using Stirling's Approximation.
These both require the ability to solve $n \log_2 n = c$, with Stirling require a little more manipulation.
Questions
Here is some python code I put together to complete the table with my current output:
EDIT: Based on a couple of answers, I have used a binary search method (except for lg n). I have edited the code below to reflect this:
```
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| f(n) | 1 sec | 1 min | 1 Hour | 1 Day | 1 Month | 1 Y
Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic complexities grow with the size of the input.
The question asks:
For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.
The time periods are 1 second, 1 minute, 1 hour, 1 day, 1 month, 1 year, 1 century.
The functions $f(n)$ are seemingly common time complexities that arise in algorithms frequently, the list being:
$$ \log_2n, \quad \sqrt{n}, \quad n, \quad n \log_2 n, \quad n^2, \quad n^3, \quad 2^n \quad \text{and} \quad n!$$
Most are fairly straightforward algebraic manipulations. I am struggling with two of these, and both for the same reason:
If $c$ is the time in microseconds, the two I am struggling with are
$$ n \log_2 n = c$$
$$ n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$$
For $n!$ I thought of using Stirling's Approximation.
These both require the ability to solve $n \log_2 n = c$, with Stirling require a little more manipulation.
Questions
- As $n \log_2 n$ is not solvable using elementary functions (only Lambert W), what are some good ways to approximate $n log_2 n$? Or how do we implement Lambert W?
- How do we solve n! = c, necessarily approximately as n grows large. Is Stirling the right way to go, and if so how to solve $\sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$
Here is some python code I put together to complete the table with my current output:
EDIT: Based on a couple of answers, I have used a binary search method (except for lg n). I have edited the code below to reflect this:
```
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| f(n) | 1 sec | 1 min | 1 Hour | 1 Day | 1 Month | 1 Y
Solution
The approximate inverse of $c = n\log n$ is $n = c/\log c$. Indeed, for this value of $n$ we have
$$ n\log n = \frac{c}{\log c} \log \frac{c}{\log c} = \frac{c}{\log c} (\log c - \log\log c) = c \left(1 - \frac{\log\log c}{\log c}\right). $$
This approximation is usually good enough.
$$ n\log n = \frac{c}{\log c} \log \frac{c}{\log c} = \frac{c}{\log c} (\log c - \log\log c) = c \left(1 - \frac{\log\log c}{\log c}\right). $$
This approximation is usually good enough.
Context
StackExchange Computer Science Q#44944, answer score: 9
Revisions (0)
No revisions yet.