# Lower bound on computing $x^n$

I know that we can compute $$x^n$$ in $$\log n$$. Are there any lower bound for computing $$x^n$$?

• What is $x$ in this context? The complexity can depend on it as well. In addition - it seems you assume that multiplication works in $O(1)$ (for any two arbitrary numbers, no matter how large they are). Assuming this may change the result of the lower bound - as one could show an $\Omega(n)$ lower bound when this isn't assumed. Nov 24 at 12:49
• To be a bit more precise - what exactly is the computational model you are working with? Nov 24 at 12:49

If $$n$$ is given as a number in some positional number system, say base 2 or base 10, then $$\Omega(\log n)$$ is a lower bound, since figuring out the value of n alone takes $$\Omega(\log n)$$ steps.
• Since we are talking about lower bound, shouldn't it be $\Omega(\log n)$? Nov 24 at 13:17