Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$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\left[\log(n)\right]^{-1}$. From this point on, I have no clue what I should do.

share|cite|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
On a semi-related note, $f(n)\in \Theta(\pi(n))$, where $\pi$ is the prime counting function. There are many options for what can go inside the parenthesis. – apnorton Feb 10 '15 at 22:04

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

share|cite|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.