2
$\begingroup$

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?

  • 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.2012-10-14

1 Answers 1

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