If you make the run lengths increase exponentially instead of linearly then you get O(k) unconditionally.
I know. I was improving the constant factor.
Ah yes, OK, essentially the same randomization helps against an adversary when you’re growing exponentially as when you’re growing only linearly. Fair enough.
If you make the run lengths increase exponentially instead of linearly then you get O(k) unconditionally.
I know. I was improving the constant factor.
Ah yes, OK, essentially the same randomization helps against an adversary when you’re growing exponentially as when you’re growing only linearly. Fair enough.