I know that we can compute $x^n$ in $\log n$. Are there any lower bound for computing $x^n$?
2
-
1$\begingroup$ 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. $\endgroup$– nir shaharNov 24, 2021 at 12:49
-
$\begingroup$ To be a bit more precise - what exactly is the computational model you are working with? $\endgroup$– nir shaharNov 24, 2021 at 12:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ Since we are talking about lower bound, shouldn't it be $\Omega(\log n)$? $\endgroup$ Nov 24, 2021 at 13:17