0

As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth?

$g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\leq c_2f(n)$ for some positive constants $c_1, c_2$ for some $n>n_0>0$. But how can I conclude $g(n)$ also satisfies the polynomial growth condition?

polynomial-growth condition

Mason Rashford
  • 489

1 Answers1

-1

Let $n_0,c_1,c_2,\hat n,\phi,d$ be as above. Then, for all $\psi\in[1,\phi]$ and $n\ge\max(n_0,\hat n),$

$$g(\psi n)\le c_2f(\psi n)\le c_2df(n)\le\frac{c_2d}{c_1}g(n)$$ and $$g(\psi n)\ge c_1f(\psi n)\ge\frac{c_1}d f(n)\ge\frac{c_1}{c_2d} g(n).$$

Anne Bauval
  • 34,650