I was recently reading a really good article on this topic, and I realize that it could be a very good added value for students to understand better and appreciate (and eventually put in practice) all the theory that is behind Algorithm Complexity1. Certainly, not everyone will apply this in the future, since the most efficient way to solve a problem is not always required (although it should be). I think more people should be interested in this, since it has benefits in various ways.
To understand my question a little bit better, I want to give an example of my own personal experience.
From the very first moment I learned about Trees and Binary Trees (a long time ago), I don't know why, I hate them. I never thought about them like a solution to the many problems I had to face and resolve. Some time ago, I was told to recreate from scratch the Shannon–Fano encoding as an exercise. I enjoyed that so much! And of course, for that encoding, everything is based on trees. It was at that point that I was more interested in trees, how they work and their functionality to solve real life problems.
So, in the same way the Shannon–Fano coding help me to understand better and made me want to go deeper in the tree's data structure theory, I'm asking for good motivating examples that might help others understand and want to learn more about Algorithm Complexity.
1 Just to clarify, when I say Algorithm Complexity, I'm talking about all the theory and techniques that are available to know how efficient an algorithm is, and to compare that information with other results, thus leading to the most efficient way to solve a problem.