4 ms·
Maybe a dumb question, but what exactly are you talking about between exponential and polynomial?
by ehsanu1 7y ago
Maybe a dumb question, but what exactly are you talking about between exponential and polynomial?
- dgacmu 7y agoIt'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-growth-between-polynomial-and-exponential https://math.stackexchange.com/questions/226628/orders-of-gr...
- mehrdadn 7y agoIt'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?