patternModerate
n*log n and n/log n against polynomial running time
Viewed 0 times
polynomiallogtimeagainstrunningand
Problem
I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\log n)$ with $\Theta(n^f)$ where $0 < f < 1$.
For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$
I would like to have some directions towards proceeding in such cases. Thank you.
For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$
I would like to have some directions towards proceeding in such cases. Thank you.
Solution
$\log n$ is the inverse of $2^n$. Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.
$n / \log n$ vs $n^k$, for $k \log n$ for large $n$, $n / \log n > n^k$ for $k < 1$ and large $n$.
$n / \log n$ vs $n^k$, for $k \log n$ for large $n$, $n / \log n > n^k$ for $k < 1$ and large $n$.
Context
StackExchange Computer Science Q#3563, answer score: 10
Revisions (0)
No revisions yet.