A little anecdote: there was a case of O(N^2) in readline with long lines. Essentially a bug in the redisplay logic. It affected Bash, mysql/psql, Python, etc.

After having suffered from this for some years, last year that annoyed me enough to start digging into readline to figure out what was causing it. In the end, that prompted Chet Ramey to come up with a fix which looks like it is now being released!

I promised myself that when this one was fixed, I'd look into why most readline shells can go nuts when you resize them - somehow they don't always discover that the line width has changed.