It's not a dumb question at all - it gets beyond most undergraduate classes on computational complexity. What's interesting is that the algorithm presented for this problem is exactly one of those classes: the quasi-polynomials, which grow exponentially in a polynomial of logs of x.

For more see: https://math.stackexchange.com/questions/226628/orders-of-gr...

It's not a dumb question! It's actually a typical exam question -- "write down a time complexity that is faster than polynomial but slower than exponential". It makes you think outside the box they spend the rest of the semester shoving you in :-) as an example, if you consider n^k is polynomial, but make k increase with n, then you can get n^log(n). Can you show that that's slower than exponential?