If $f(x) \in \Theta(g(x))$ can we imply that $f(x^2) \in \Theta(g(x^2))$ and $f(\log x) \in \Theta g(\log x)$?

51 Views Asked by At

My first thought is that it is, because $\Theta$ is a tight bound, so assuming a let's say $f(x) = x +2$ and $g(x) = x$, $f(x^2)$ should be bound by $\Theta(g(x^2))$. Same for the logarithm as well.

However, I do need clarification about this for the cases where the limits of $f(x)$ and $g(x)$ tends to infinity and not.

1

There are 1 best solutions below

0
On

Yes, for $x \to +\infty$ these are all true. But I don't know what you mean by "$\Theta$ is a tight bound". It's just that there are $A, B, C > 0$ such that $A g(x) < f(x) < B g(x)$ for all $x > C$, and therefore $A g(x^2) < f(x^2) < B g(x^2)$ for $x > \sqrt{C}$ and $A g(\log(x)) < f(\log(x)) < B g(\log(x))$ for $x > \exp(C)$.