Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.