0
$\begingroup$

I am required to identify if $\log{(f(x))}$ is a subset of $O(\log{n})$ holds true for all polynomial functions. If I try with $f(x) = x^2$, then I am able to prove it to be correct. But, with $f(x) = -2(x+2)(x-7)$, I am unable to prove it.

Am I missing something? Please advise.

Thanks

  • 1
    Note that $x^m\le x^n$ for $m\le n,x\ge1$ implies that $P(x)=a_dx^d+\cdots+a_0\le(a_d+\cdots+a_0)x^d$ for $x\ge1$ which is obviously $O(x^d)$.2011-09-28

1 Answers 1

1

Assuming $\lim_{x\to\infty} p(x) = \infty$ as otherwise it doesn't make sense.

First, if $p(x)=a_nx^n+\cdots+a_0$ then there exists $C$, such that for all sufficiently large $x$, $p(x) \leq C x^n$ (a suitable $C$ would be $a_n+1$).

Second, $\forall D,E$ exists $F$, such that $D\log x+E \leq F\log x$ for all sufficiently large $x$ (you can take $F$ to be $D+1$ for example).

Now, for sufficiently large $x$: $\log p(x) \leq \log (C x^n) = \log C + n\log x \leq D \log x .$

If $\lim_{x\to\infty} p(x) = -\infty$ a sensible question to ask would be if $\log |p(x)|\in O(\log x)$.