1
$\begingroup$

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?

A function $f(n)$ defined on all sufficiently large positive reals satisfies the polynomial-growth condition if there exists a constant $\hat{n} > 0$ such that the following holds: for every constant $\phi \geq 1$, there exits a constant $d>1$ (depending on $\phi$) such that $f(n)/d \leq f(\psi n) \leq d f(n)$ for all $1 \leq \psi \leq \phi$ and $n \geq \hat{n}$.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Let us consider only sufficiently large values of $n$. As you have pointed out there are two constants $c_1, c_2$ with $0< c_1 \le c_2$ such that: $$ c_1 f(n) \le g(n) \le c_2f(n). $$

Also, since $f$ has polynomial growth, for every $\phi \ge 1$ there exists some $d_\phi > 1$ such that: $$ \frac{1}{d_\phi} f(n) \le f(\psi n) \le d_\phi f(n) \quad \forall 1 \le\psi \le \phi. $$

Then the following holds for all $1 \le\psi \le \phi$: $$ \frac{c_1}{c_2 d_\phi} g(n) \le \frac{c_1 }{d_\phi} f(n) \le c_1 f(\psi n) \le g(\psi n) \le c_2 f(\psi n) \le c_2 d_\phi f(n) \le \frac{c_2 d_\phi}{c_1} g(n). $$ Which means that $g$ also satisfies the polynomial growth condition. In particular, for a given $\phi$, we can choose $d'_\phi = \frac{c_2 d_\phi}{c_1}$ to obtain: $$ \frac{1}{d'_\phi} g(n) \le g(\psi n) \le d'_\phi g(n) \quad \forall 1 \le\psi \le \phi, $$ where $d'_\phi > 1$ holds since $c_2 \ge c_1$ and $d_\phi > 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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