[Solved]: From Guido’s essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

Read the list in chunks of $k$, convert them to strings, and sum the chunks.

Creating each chunk takes time $Theta(1+2+cdots+k) = Theta(k^2)$, and we do this $n/k$ times, for a total of $Theta(nk)$. Adding the chunks takes time $Theta(k+2k+cdots+n) = Theta(k(1+2+cdots+n/k)) = Theta(k(n/k)^2) = Theta(n^2/k)$. In total, we get a complexity of $Theta(n(k+n/k))$. The optimal choice of $k$ is $sqrt{n}$, and this gives a complexity of $Theta(n^{3/2})$. In contrast, the trivial algorithm has $k = 1$ and so complexity $Theta(n^2)$. More generally, you can consider $d$ levels of recursion. Let $f_d(n)$ denote the optimal complexity of such a scheme, measuring just the merging steps. Clearly $f_1(n) approx n^2/2$. Given an algorithm with $d$ levels, we can construct a $d+1$-level algorithm which cuts the input into chunks of length $k$, runs the $d$-level algorithm on each of them, and concatenates the result. This takes time roughly $(n/k)f_d(k) + n^2/2k$. For example, $$ begin{align*} 2f_2(n) &approx max_k nk + n^2/k approx 2n^{3/2} & (k=sqrt{n}), 2f_3(n) &approx max_k 2nk^{1/2} + n^2/k approx 3n^{4/3} & (k=n^{2/3}), 2f_4(n) &approx max_k 3nk^{1/3} + n^2/k approx 4n^{5/4} & (k=n^{3/4}). end{align*} $$ We get that $2f_d(n) approx dn^{(d+1)/d}$. Calculus shows that the best choice of $d$ is $d = log n$, in which case we obtain $2f_{log n}(n) = Theta(nlog n)$. However, this scheme is not necessarily achievable. If we choose a branching factor of 2 then we get an algorithm whose running time is $Theta(nlog n)$ which resembles merge sort. In fact, the sorting lower bound gives a lower bound of $Omega(nlog n)$ on any such merging procedure. We can also prove the lower bound directly. For a sequence $sigma_1,ldots,sigma_m$ of chunk lengths summing to $n$, define its potential by $$ Phi(vecsigma) = nH(X_{vecsigma}), text{ where } Pr[X_{vecsigma} = i] = frac{sigma_i}{n}. $$ Here $H$ is the entropy function. The potential function starts at $Phi(1,ldots,1) = nlog n$ and ends up at $Phi(n) = 0$. Suppose that $vectau$ is obtained from $vecsigma$ by merging $sigma_i$ and $sigma_j$ to a new chunk $tau_k$. We can sample $X_{vecsigma}$ by first sampling $X_{vectau}$, and if the result is $k$, sample according to the marginal distributions $frac{sigma_i}{sigma_i+sigma_j},frac{sigma_j}{sigma_i+sigma_j}$. Calculation shows that $$ begin{align*} Phi(vecsigma) = nH(vecsigma) &= nH(vectau) + nPr[X_{vectau}=k] hleft(frac{sigma_i}{sigma_i+sigma_j}right) &= Phi(vectau) + (sigma_i+sigma_j) hleft(frac{sigma_i}{sigma_i+sigma_j}right) &= Phi(vectau) + O(sigma_i+sigma_j). end{align*} $$ Here $h$ is the binary entropy function. This shows that the potential difference is a lower bound on the running time. Since the overall potential difference is $nlog n$, we obtain a lower bound of $Omega(nlog n)$. Furthermore, the calculation shows that it’s best to always merge chunks of identical size.