I'm doing some reading up on Big O, Omega and Theta. From what I understand if $f(n)$ is Big O ($f(n) \leq c\cdot g(n)$) and $f(n)$ is Big Omega ($f(n) \geq c\cdot g(n)$), then $f(n)$ is Big Theta. If I'm able to find a constant $c$ and $n$ such that ($f(n) = c\cdot g(n)$), does that mean $f(n)$ is automatically Big Theta since the equals part of the definition for Big O and Big Omega are satisfied?

For instance I'm trying to prove $100n + \log n \leq c\cdot n+(\log n)^2$. I found that if $n = 10 $ and $c = 91$, then both sides of the equation are equivalent to $1001$.

  • $\begingroup$ Statements like "f is big O", "f is big omega", and "f is big theta" are ungrammatical. It's similar to saying "f is taller than", "f is shorter than", and "f is about the same height as". You have a subject but no object. The correct way to say them is "f is big O of g", "f is big omega of g", and "f is big theta of g". $\endgroup$ – Antonio Vargas Sep 27 '16 at 8:56

When doing asymptotic analysis, you need to remember that in statements such as $$f(n) \geq c g(n)$$, while $c$ is just a particular value, the statements are meant to apply to all $n$ (or all $n$ above some $n_0$).

You have found one particular $n$ for which an inequality holds; that says nothing about asymptotic behavior.

On the there hand, if you could prove that for all $n$ (or all $n$ above some $n_0$) and some particular $c$, $f(n) = cg(n)$ then indeed $f(n) = \Theta(g(n))$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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