Oh, I skimmed over the O(1) part. That baffled me for a moment, then I realized you were talking about the general case of a uniform random input where a carry

Oh, I skimmed over the O(1) part. That baffled me for a moment, then I realized you were talking about the general case of a uniform random input where a carry for the 1s digit has probability 0.1, a carry for the 10s digit 0.01, etc., and all 9s is the pathological worst case, right? That's what I get for coming into the discussion sideways.