Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following was posted from a lecture:

"($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method.

$Z_1 = a \bmod N$

$Z_2 = (aZ_1) \bmod N$

$Z_3 = (aZ_2) \bmod N$

. . .

$Z_n = (aZ_{n-1}) \bmod N$

Taking |a| = |N|, the runtime complexity of ($a^n \bmod N$) is $\mathcal{O}(n*|N|^2)$ The usual approach to computing $a^n \bmod N$ is inefficient as it is exponential in $n$."

How is $\mathcal{O}(n*|N|^2)$ exponential in $n$? It appears polynomial in $n$ to me. Can someone explain? Thanks.

share|improve this question
2  
My guess is that they mean it is linear in the exponent $n$, but exponential in the length of the exponent. Often, complexity of an algorithm is given in terms of the length of the input, not the numeric value of the input. –  Daan Michiels Oct 23 '12 at 20:25
add comment

1 Answer

up vote 3 down vote accepted

$O(n \cdot |N|^2)$ is linear in $n$, but exponential in the length of $n$, which is $\Theta(\log(n))$.

Since the input is presumably written in binary (or any base other than unary), this means that the runtime is exponential in the size of the input.

share|improve this answer
    
Thanks, but not sure I fully understand. The complexity of addition is noted as $\Theta(n)$ en.wikipedia.org/wiki/… Does this mean that addition is exponential in the length of $n$? –  SPSmith Oct 26 '12 at 12:27
1  
On the wikipedia page, the input is described as "Two $n$-digit numbers". So $\Theta(n)$ is linear in the length of the input. In general, whenever you read a running time, always ask yourself what the $n$ is referring two -- both (1) the number of bits and (2) the value being represented are common idioms, so you need to decide based on context which is being used. –  Jeremy Hurwitz Oct 27 '12 at 15:11
    
Got it. Thanks. –  SPSmith Oct 27 '12 at 16:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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