Each JacobiGivens rotation can be done in O(''n'') steps when the pivot element ''p'' is known. However the search for ''p'' requires inspection of all ''N'' ≈ {{sfrac|1|2}} ''n''<sup>2</sup> off-diagonal elements. We can reduce this to O(''n'') complexity too if we introduce an additional index array <math> m_1, \, \dots \, , \, m_{n - 1} </math> with the property that <math> m_i </math> is the index of the largest element in row ''i'', (''i'' = 1, ..., ''n'' − 1) of the current ''S''. Then the indices of the pivot (''k'', ''l'') must be one of the pairs <math> (i, m_i) </math>. Also the updating of the index array can be done in O(''n'') average-case complexity: First, the maximum entry in the updated rows ''k'' and ''l'' can be found in O(''n'') steps. In the other rows ''i'', only the entries in columns ''k'' and ''l'' change. Looping over these rows, if <math> m_i </math> is neither ''k'' nor ''l'', it suffices to compare the old maximum at <math> m_i </math> to the new entries and update <math> m_i </math> if necessary. If <math> m_i </math> should be equal to ''k'' or ''l'' and the corresponding entry decreased during the update, the maximum over row ''i'' has to be found from scratch in O(''n'') complexity. However, this will happen on average only once per rotation. Thus, each rotation has O(''n'') and one sweep O(''n''<sup>3</sup>) average-case complexity, which is equivalent to one matrix multiplication. Additionally the <math> m_i </math> must be initialized before the process starts, which can be done in ''n''<sup>2</sup> steps.
Typically the Jacobi method converges within numerical precision after a small number of sweeps. Note that multiple eigenvalues reduce the number of iterations since <math>N_S < N</math>.
