1
$\begingroup$

I was wondering if $f(x)=O(x^{c+a})$ for all $a>0$ then is it necessarily true that $f(x)=O(x^c\log x)$? I suspect it's not true but want to know why. (I know the converse is true.)

Any help is much appreciated, Thank you.

$\endgroup$
1
  • $\begingroup$ I think another example is (x^c)logxlogx $\endgroup$
    – user3785
    Dec 16, 2010 at 14:46

2 Answers 2

6
$\begingroup$

Consider $f(x) = x^c (\log x)^b$, where $b>1$. This function is $O(x^{(c+a)})$ but it is not $O(x^c \log x)$.

$\endgroup$
1
  • $\begingroup$ I don't quite see how f is big O of x^(c+a) for all a>0. How does one show it? $\endgroup$
    – user3785
    Nov 23, 2010 at 12:12
0
$\begingroup$

Consider $f(x) = (\log x)^2$.

$\endgroup$

You must log in to answer this question.