Skip to main content
4 of 4
deleted 277 characters in body
D.W.
  • 165.6k
  • 21
  • 230
  • 490

Time complexity of Jacobi symbol

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?

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.

Lereu
  • 111
  • 3