0
$\begingroup$

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

$\endgroup$
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 shahar
    Nov 24 at 12:49
  • $\begingroup$ To be a bit more precise - what exactly is the computational model you are working with? $\endgroup$
    – nir shahar
    Nov 24 at 12:49
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Since we are talking about lower bound, shouldn't it be $\Omega(\log n)$? $\endgroup$
    – Nathaniel
    Nov 24 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.