3

I know that by the assumption that $f ∈ Θ(g)$ we know that there exist constants $c_0$ and $c_1$ in $\mathbb R^+$, and there exists $n_0 ∈ \mathbb N$ such that:

$$c_0 \cdot g(n)\le f(n)\le c_1 \cdot g(n),$$

but this is then where I get stuck, can anyone help me out?

Hagen von Eitzen
  • 374,180
Hannah
  • 73
  • 3
    can anyone help me out? Yes I can: continue by writing down what $g\in\Theta(h)$ means, like you did for $f\in\Theta(g)$, and the light will come. – Did Oct 14 '12 at 10:55

1 Answers1

1

Try this:

$$ c_2 g(n) \leq f(n) \leq c_1 g(n)\\ c_4h(n) \leq g(n) \leq c_3 h(n) $$

Now plug in the bounds for $g(n)$ in the first inequality: $$ c_2 c_4 h(n) \leq f(n) \leq c_1 c_3 h(n) $$ Since $c1 \cdot c3=c'$ and $c2 \cdot c4=c''$ are both constants: $$ f(n)=\Theta (h(n)) $$

Alex
  • 19,262