Message Boards Message Boards

0
|
2038 Views
|
0 Replies
|
0 Total Likes
View groups...
Share
Share this post:

How can I express time complexity as a function of the number of bits?

Posted 9 years ago

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?

POSTED BY: Hey Hey
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract