2
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .