Using a linked-list where the actual access pattern is random and an hash table is more suitable would be the most obvious, especially since this is C code.

Similar things includes C-style string functions like strlen() and so on that require iterating over an unknown length array. Caching (or better avoiding!) this work can save a lot of computing time. Example from libgit2: https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f...

In fact C-style string is a rich source of O(n) performance issues. And git is full of strings like filenames.

It's an issue where processing something took O(n) time, when an algorithm to process it asymptotically more quickly (say O(log n)) would be more appropriate.

The old code probably works properly for the average case, but will really blow up on pathological cases. My best personal example was an optimisation pass that turned out to be exponential in the worst case. On average `n` was small, so no-one cared, until a pathological case came up where compile time ballooned to over half-an-hour. Working out that the operation could be done in a linear way only shaved a fraction of a second off the average case, but brought the half-hour case down to a few seconds.

"O(n) issue" is generic for some asymptotic optimization issue. It doesn't literally mean it was running in O(n) and there was a better O(n log n) solution. It could be O(n^2) and there was an O(n) solution or O(n) when there was an O(log n) solution or O(n!) when there was an O(n^2) solution. It just means there was a poor algorithm choice / design decision for some part of the code when a more efficient option is available.

It's notation denoting the performance of an algorithm. See https://en.wikipedia.org/wiki/Big_O_notation