# Relationshop between Theta and little-o (Big-O notation)

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

true?

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.

• Well, take $f(n) = n$ and $g(n) = 2n$. Feb 11, 2014 at 16:21

## 1 Answer

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