If there exists $c$ and $k$ such that $f(n) = c \cdot g(n)$, is $f(n)$ big theta?

202 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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