I have an algorithm that runs in
$O\left(\sqrt{x}\right)$, where
$x$ the my input.
Now, instead of using
$x$, I would like to use the number of bits of
$x$, i.e.
$n$. I know that
$x = \Theta(2^n)$, therefore my algorithm should be
$O\left(\sqrt{x}\right) = O(2^{n/2})$. Is it right?
What I cannot understand is that, as far as I know,
$O(2^{n/2})$ is equivalent to
$O(2^n)$ (in other words:
$2^n$ and
$2^(n/2)$ grow at the same rate). But this can't be right, because it would imply that
$O\left(\sqrt{x}\right)$ is equivalent
$O(x)$, which is false (
$x$ and
$\sqrt{x}$ don't grow at the same rate).
What am I doing wrong?