My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which n should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?
If the sequence is periodic then the linear complexity of the sequence will not change after some point. Remember, an LFSR with length $L$ can produce a periodic sequence at most length $2^L-1$ if the minimal polynomial is maximal.
But the Berlakamp-Massay algorithm cannot detect the period, it must process all inputs. It works interactively such that it updates the internals if a new bit cannot match the output, i.e. there is a discrepancy. Once the period is reached it will not update the internals but the algorithm can only be modified to output the last modified internal distance.
If you know the period, you can stop the Berlakamp-Massay after processing $N$ bits. The reason can be seen as in the next extreme example. Consider the periodic sequence where in the period it has 99-zero followed by 1.
$$\overbrace{\underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}}^{\text{ the preiod}}\, \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots$$
The linear complexity of this sequence is 100. Therefore you have to process all of the period to find the linear complexity of the sequence.
The definition doesn't seem to give any clear idea of computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop
Because it is designed to produce the LFSR that produces the given sequence, nothing more. As said before it must process all of the inputs.
If you want to find the period use period finding algorithm like Z-algorithm
