0

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$.

babakks
  • 1,640
Extreme112
  • 253
  • 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". – Antonio Vargas Sep 27 '16 at 08:56

1 Answers1

1

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))$.

Mark Fischler
  • 41,743