Many years ago, as an undergrad, I was telling a grad student friend how I'd been learning about the Selection algorithm- it lets you pick the Kth largest element from an unsorted list in linear time, which is pretty neat.

I said "It's O(n), but the constant is ridiculous in most implementations so it's usually better just to sort and then pick the kth element". The grad student friend said something that stuck with me: "Sure, but the algorithm proves it's possible to find the kth element in linear time. That was never guaranteed. Now we just need to find a better way to do it."

Random conversation that stuck with me, and they probably forgot it a moment later.