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?