[karmakaze]

Ending up at sqrt(n) doing a visual linear regression on a log plot doesn't mean the same thing to me. It would be better to frame the discussion as an illustration of the limitations of big-O analysis in real world cases, than to say that the big-O of a linked-list is really O(sqrt(N))

[Dylan16807]

There's certainly a difference between showing a plot such that it seems to be O(sqrt(N)) and proving that it's O(sqrt(N)).

But you're still saying O(sqrt(N)) in both of those. I think it's useful to use the term O(sqrt(N)). It's the best notation for the job.