Time complexity of Jacobi symbol

Question

Here is my algorithm with inputs $a$, which is an integer and $n$, which is an odd natural. Is $\mathcal{O}(n)$ the time complexity of this algorithm?

My thoughts:

The if-cases in the lines $1$ up to $20$ and $32$ up to $37$ are checked in $\mathcal{O}(1)$.

In lines $21$ and $22$, the symbol is reduced. My guess it that this can happen at most $n$ times, so this would be $\mathcal{O}(n)$.

The remaining if-case in line $24$ divided the number $a$ by $2$ as often as possible. This is done in $\mathcal{O}(\log_2(n))$ times.

So since $\mathcal{O}(n)$ is the dominating term here, I suppose that this is the time complexity of this algorithm.

Answer 1

I haven't checked carefully, but the running time is most likely $\mathcal{O}(\log \max(a,n))$ iterations, or $\mathcal{O}((\log \max(a,n)) \cdot (\log n)^2)$ bit-operations. In the special case where $a \le n$, we can describe this as $\mathcal{O}(\log n)$ iterations or $\mathcal{O}((\log n)^3)$ bit-operations. Good algorithms for evaluating the Jacobi symbol have that running time. As a quick glance at your pseudocode, it looks like the algorithm you present has that running time too.

For lines 21-22, at a first glance, it looks like those might get executed up to $n$ times, but a more careful analysis shows that this is overly pessimistic.

Suppose that the running time when $a \le n$ is $\mathcal{O}((\log n)^3)$ bit-operations. Then if you invoke it with $a > n$, it will take $\mathcal{O}((\log a)(\log n)^2)$ time to compute $a \bmod n$, and then $\mathcal{O}((\log n)^3)$ time to compute the recursive call. The former dominates, so the total running time in this case is $\mathcal{O}((\log a)(\log n)^2)$, as claimed.

You might be concerned about how lines 21-22 and line 37 interact. However, after every 5(?) invocations, the value of $n$ is reduced by at least factor of $4/3$. $(a,n)$ becomes $(n,a)$, which becomes $(b,a)=(n \bmod a, a)$, which becomes $(a,b)$, which becomes $(c,b)=(a \bmod b, b)$, which becomes $(b,c)$, and $c \le 4n/3$. A similar thing happens with the Euclidean algorithm for computing the gcd; see standard analyses of it for more details, e.g., https://stackoverflow.com/q/3980416/781723.

I might be getting a few details wrong, so please check my reasoning carefully yourself, but I think the general gist here is probably correct.

Of course, $\mathcal{O}((\log n)^3)$ is smaller than $\mathcal{O}(n)$. So yes, you could say that the running time is $\mathcal{O}(n)$, but that would be an extremely loose and misleading upper bound on the running time.