> Why am I not taught a single algorithm whose complexity is between these? is my question.
Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2.
There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step."
It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.
> Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2. There are the algorithms for factoring large numbers, and the graph isomorphism problem.
I assume you mean "interesting" ones? Since they could just show a program that counts up to n^log(n) and voila, you have a super-polynomial sub-exponential algorithm.
Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2.
There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step."
It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.