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?