Each addition is linear in d, but there are d additions, so it's already quadratic before you even consider the multiplications. In a power-of-2 base, the resu

Each addition is linear in d, but there are d additions, so it's already quadratic before you even consider the multiplications. In a power-of-2 base, the result of the multiplication is a constant number of digits (because the multiplication is just a shift of a single digit), so the additions could each be constant time in that case.