Is $$ f(n) \in \Theta(g(n)) \Leftrightarrow f(n) = g(n) \cdot (1+o(1)) $$


For clarity, here are the definitions I use: $$ f(n) \in o(g(n)) \Leftrightarrow \forall \epsilon > 0 \exists n_o\forall n> n_0: |f(n)|\leq \epsilon \cdot |g(n)| $$ $$ f(n) \in O(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: |f(n)|\leq c \cdot |g(n)| $$ $$ f(n) \in \Omega(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: c \cdot |g(n)| \leq |f(n)| $$ $$ f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \Omega(g(n)) \land f(n)\in O(g(n)) $$

What I have so far:

The $\Leftarrow$ direction is quite easy:

$$ f(n) \in o(g(n)) \Rightarrow f(n) \in O(g(n)) \land g(n)+o(1)\cdot g(n) \in \Omega(g(n)) $$

However, I am unsure about the other direction. I suspect that it's not, but can't proof it.

PS: This is not a homework assignment, but homework related: I am working on a seminar paper and want to understand this.

  • 4
    $\begingroup$ Well, take $f(n) = n$ and $g(n) = 2n$. $\endgroup$ – Karolis Juodelė Feb 11 '14 at 16:21

To expand slightly on Karolis's comment, you can get a counterexample by taking for any strictly positive function $f$ and, for any constant $\delta>0$, the function $(1+\delta)f(x)$. $(1+\delta)f(x)\in \Theta(f(x))$ but $(1+\delta)f(x)\notin (1+o(1))f(x)$ since, for $\epsilon<\delta$, it is not true that $(1+\delta)f(x)\leq (1+\epsilon)f(x)$.

| cite | improve this answer | |

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.