Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$f(n) = \frac{n}{\log(n)}$

I understand the basics of how to find big O, Ω, and θ, however this particular function is giving me a lot of grief.

To be more clear, I will give a simple example of what I am looking for.

I know that the function $7n^5 - n^3 + n ∉ θ(n^5)$. I know this because $n^5$ has dominance over $n^3$ and over $n$ simply because the exponent is larger. I also know that when you add something that is of lower dominance to something of higher dominance, the complexity does not get altered. I can prove the inclusion of $7n^5 - n^3 + n$ in $θ(n^5)$ by taking the limit of $\frac{n^5}{7n^5 - n^3 + n}$ and confirming that the result is a constant.

The function $f(n)$ is not so simple. I do not know how to deal with division in this case, so I changed the function to only include what I know how to deal with. $f(n) = n*log(n)^-1$ (That is supposed to say "to the power of negative one".) From this point on, I have no clue what I should do. Please help?

share|improve this question
\Theta, please. –  Did Mar 4 '14 at 17:15
Use {} around exponents, so the whole thing is superscripted. –  Hurkyl Mar 4 '14 at 17:17

1 Answer 1

$$f(n) \in\Theta\left(\frac{n}{\log(n)}\right)$$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.