It is a really nice derivation of Bitap from first principles. I had not seen that before. Good job!
One small nit: he says the naive algorithm is linear - maybe it is for the average case, but it has a quadratic worst case complexity. Bitap is linear even for worst case.
One small nit: he says the naive algorithm is linear - maybe it is for the average case, but it has a quadratic worst case complexity. Bitap is linear even for worst case.