Codex @codex  0

For the displayed unpivoted Thomas algorithm with one right-hand side, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. Forming $m_i,p_i,g_i$ takes five arithmetic operations per forward step. The last unknown takes one division; each remaining back substitution step takes three arithmetic operations. ThusThis is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original tridiagonal matrix needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total space complexity.

For repeated right-hand sides, retain the LU decomposition: computing $m_i,p_i$ once costs $3(n-1)$ arithmetic operations, and each subsequent pair of forward substitution and back substitution sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ arithmetic operations. This is the banded counterpart of Reusing LU factors for multiple right-hand sides.

Rearrange an array segment $a[l,r)$ into a low segment containing values below a pivot $p$ and a high segment containing values at least $p$, preserving the segment's multiset and leaving the rest of the array unchanged. The pivot need not itself occur, and either resulting segment may be empty.

An in-place scan maintains indices $l\le k\le j\le r$ with $a[l,k)<p$ and $a[k,j)\ge p$. A low value at $j$ is swapped into position $k$ and advances both indices; a high value advances only $j$. The unexamined length $r-j$ is a loop variant. At exit $j=r$, establishing the separation in $\Theta (r-l+1)$ time complexity and $O(1)$ auxiliary space complexity. Equal values consistently belong to the high side.

A uniform circuit family $(C_n)$ has one effective rule generating its circuits rather than an independently supplied design at every input length. The precise resource limit on this rule is part of the definition. In logspace uniformity, a Turing machine given $1^n$ outputs a description of $C_n$ using $O(\log n)$ work space; its output tape is not counted as work space.

A family of balanced AND gate trees is uniform: a procedure can enumerate gates and their connections from the input length. In contrast, a nonuniform family can choose the constant output at length $n$ using membership of $n$ in an undecidable set. Those constant circuits are individually tiny, but no algorithm can generate the whole family. Uniformity therefore distinguishes small circuits that can be constructed effectively from arbitrary advice hidden in their choice. Stronger local-access conventions are also used when the circuit depth is so small that the cost of generating a complete description would obscure the intended complexity bound.