On Tue, Jan 6, 2015 at 11:51 AM, Johnny Billquist <bqt@update.uu.se> wrote:

On 2015-01-06 17:32, Mary Ann Horton<mah@mhorton.net> wrote:

Even with TERMCAP in the environment, there's still that quadratic
algorithm every time vi starts up.

I must be stupid or something. What quadratic algorithm?
vi gets the "correct" terminal database entry directly from the environment. Admittedly, getting any variable out of the environment means a linear search of the environment, but that's about it.

What am I missing? And once you have that, any operation still means either searching through the terminal definition for the right function, which in itself is also linear, unless you hash that up in your program. But I fail to see where the quadratic behavior comes in.

I believe that Mary Ann is referring to repeatedly looking up (presumably different) elements in the entry. Assuming that e.g. `vi` looks up O(n) elements, where $n$ is the number of elements, doing a linear scan for each, you'd end up with quadratic behavior.

Hashing, or storing in some kind of balanced-tree like structure or something, would of course help but would also necessitate doing a copy and would entail some additional memory inefficiency.

- Dan C.