I too very much liked algorithms in college ... well, I found that theoretical part of it to most employers has as much value as ... snow.
I will tell you, #2 and #3 are pretty much useless in the real world (in my 6 years as employee in 3 places), unless you are doing industrial research, which is a rare type of position. I would say concentrate on compilers - they are a bit tricky algorithmically, plus they make you a much better and more employable programmer.
Implementation of databases is also quite tricky, but that would be specializing, while knowledge of compilers is a more universal tool.
If you also like math, then machine learning knowledge is very applicable and well-rewarded these days.
To my critics: So ... you two alternative implementations, and you have proved that the complexity of both is O(m*log(n) + nk^2). Ok, two things come to my mind:
A) Did you really need to get a master's degree in complexity theory to come up with that, or would a single undergraduate intro class to algorithms suffice (you can use Wikipedia and Google at work and read a bit).
B) Great, you proved that the complexity the same, but what are the constants? How do two algorithms measure up, particularly if constants do differ and it is now the case of comparing apples to oranges?
C) Do you use caching? Make many calls to the database? These things are very important, and I still wager that #2 and #3 are useless 95% of the time. And when they are not, deducing, and maybe even proving the formula should take at most a couple of days. Relative to that work, a lot more effort is needed to measure things empirically (yes, it is a black box, and hence performance testing is an art). Given that we have derived formulas first, we will know what are likely the important parameters, and then change those while keeping everything else fixed. If there is time and resources left, we could get more data to fill a volume. Of course, one would have to repeat the trials a bunch of times, to compute some basic statistics, and perhaps to try things out under unusual loads. That is hard work, but in my mind it has a lot more value than just the formula itself. Often the programmer just has to make an intelligent choice between a list, and array, a tree or a dictionary. On the rare occasion when a thorough performance analysis is required, still very little theory is required. The most important piece is profiling.
Therefore, I believe it would be wasteful to do a Master's degree / PhD in theory of computation / complexity and planning to work as a software developer. It surely helps to flex the brain muscles, and there is something to be said about pursuing one's love, but if one wants to be a developer, and one likes math (even if discrete), there are still better ways of getting education, having fun and being prepared for the industry.