I took a class with Prof. Traub, he would explain a problem, ask us to come up with an algorithm and then always ask "Can we do better?" and push us to find a better solution, he repeated it so often that every time I think about solving something "Can we do better?" is at the back of my mind.

He was interested in optimal algorithms and was one of the founders of the field of "information-based complexity": https://en.wikipedia.org/wiki/Information-based_complexity