What is the fastest addition algorithm on a turing machine?

Question

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$.

Answer 1

(This should be a comment but I can't comment yet)

Just to clarify, when you have an integer $n$, it's represented on $\operatorname{size}(n)=\log_2 n$ bits.

So here, you are given $n_1$ and $n_2$ and you want to compute $n_1+n_2$. Let $f(n_1, n_2)$ be the number of steps needed to compute that. You seem to be claiming that $f(n_1, n_2)=O\left((n_2)^2\right)=O\left(\left(2^{\operatorname{size}(n_2)}\right)^2\right)$, which is obviously false. Now if you change it to $f(n_1, n_2)=O\left((\operatorname{size}(n_2))^2\right)=O\left((\log_2 n_2)^2\right)$, it becomes a little bit more plausible.

But that still can't be the complexity because if you have $n_1=2^{k}-1$ and $n_2=2^0$, your algorithm will at least read $n_1$, which takes $O\left(\operatorname{size}(n_1)\right)=O\left(\log_2 n_1\right)=O(k)$ while $O\left((\log_2 n_2)^2\right)=O(1)$ in these cases. The complexity should depend on the size of $n_1$ one way or another.