How we compute the computation complexity of an exponential function like $a^x$ where $a,x \in \mathbb{Z}$ with $|a|=l$ bits and $|x|=m$ bits? Can anyone please explain using big notation?

  • 1
    $\begingroup$ See here: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus Apr 1 '18 at 15:29
  • $\begingroup$ @nbro, I've corrected my mistake for typing $b$ instead of $x$. can you please suggest a good article or book section for Big-O notation and computational complexity measure? $\endgroup$ – Tushar Saha Apr 2 '18 at 2:35

The result has roughly $l\cdot x=l\cdot 2^m$ bits. Hence $\Omega(l\cdot 2^m)$ is a lower bound both for the time complexity and thus for the running time of every specific algorithm.

On the other hand, let's look at one specific algorithm. The exponentiation can be done with $\Theta(m)$ multiplications, the $i$-th of which dealing with numbers of $\Theta(l\cdot 2^i)$ bits. Multiplication of $n$ bit numbers can be done in $\Theta(n\cdot\log n)$ time. This gives a total of

$\Theta\left(\sum_{1\leq i\leq m}l\cdot 2^i\cdot\log(l\cdot 2^i)\right)$

$=\Theta\left(l\cdot\log l\cdot\sum_{1\leq i\leq m}2^i + l\cdot\sum_{1\leq i\leq m}2^i\cdot i\right)$

$=\Theta\left(l\cdot\log l\cdot 2^m+l\cdot m\cdot 2^m\right)$

$=\Theta(l\cdot(\log l+m)\cdot2^m)$

Here we have a matching upper and lower bound for the running time of the algorithm. On the other hand, it is just one algorithm, so for the time complexity all it gives us is an upper bound $O(l\cdot(\log l+m)\cdot 2^m)$. Observe that it does not match the lower bound from above.

| cite | improve this answer | |
  • $\begingroup$ The question specifically asks for big notation, but yours seems to be the ordinary size! $\endgroup$ – David Richerby Apr 1 '18 at 16:45
  • $\begingroup$ @DavidRicherby: I read "big notation" as a shorthand for "big $O$/$\Omega$/$\Theta$-notation". I am not aware of any other meaning of the term. Please enlighten me. $\endgroup$ – kne Apr 1 '18 at 21:54

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.