What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are written out in the usual decimal expansion, and the output on the tape is just the result, $a_1+a_2$ (there is no need to keep the inputs). The best I can do so far is $O(n^2)$ time using this program I made: http://morphett.info/turing/turing.html?185f35a035e386d2a927c15b869b422a
The way this algorithm works is by finding the rightmost "non-added" digit of the number to the right of the addition sign (henceforth No. 2), marks this with an "o", and moving left until it finds a "non-added" digit of the number to the left of the addition sign (henceforth No. 1) and marking the result with a letter so that the machine will know how many decimal places to go to the left when adding next time. If there are any carries, these places are marked with numbers rather than letters because they haven't been 'reached' yet other than by the carry. The machine ends when all the digits on the right-hand number have been turned into "o"s and the machine encounters the plus sign instead of a number. Then, it cleans up all the "o"s and transforms all the letters into numbers and deletes any 0's at the beginning of the number.
I won't provide a rigorous proof, but this algorithm can be seen to be $O((n_2)^2)$ time complexity intuitively by the fact that for each digit in No. 2, the turing machine has to move about $n_2$ (which I use to denote the length of $a_2$) steps to the left, and since there are $n_2$ digits in No. 2, this algorithm takes about $n_2\times n_2=(n_2)^2$ steps. (Thus it runs in $O(n^2)$ time, assuming both numbers are of the same length, $n_1=n_2=n$). This improves on the naïve exponential time implementation of just subtracting one from No. 2 and adding one to No. 1 until No. 2 is exhausted, but is there any faster algorithm?
EDIT: Just to clarify I want the fastest algorithm for adding two decimal numbers of equal length, $n$. I use $n_1$ and $n_2$ as the lengths of $a_1$ and $a_2$ respectively only to emphasize that the algorithm is technically only quadratic in $n_2$, which is where it gets the $O(n^2)$ runtime from. I tried calculating the exact number of steps the algorithm takes, which is $n_1+2(n_2)^2+5n_2+max(n_1,n_2)+5+2c+d$, where c is the number of carries (bounded by $n_1$) and d is the number of digits in the result. Thus, a more precise runtime would be $O((n_2)^2+n_1)$, but left this out for conciseness and because in the end I only cared about the case $n_1=n_2=n$.