So when you look at the per-operation cost (t/s in my model) then what emerges is, indeed, logarithmic (r2 ~ .96 for lm(t/s ~ s + log(s)). Bounded, for sure, but if you walk in with a vector-indexing-bound but array-size-independent algorithm expecting that the performance for 1e3 elements will be representative of the behavior for 1e6, you're in for a surprise.
So when you look at the per-operation cost (t/s in my model) then what emerges is, indeed, logarithmic (r2 ~ .96 for lm(t/s ~ s + log(s)). Bounded, for sure, but if you walk in with a vector-indexing-bound but array-size-independent algorithm expecting that the performance for 1e3 elements will be representative of the behavior for 1e6, you're in for a surprise.