Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I am not aware of the difference. Is it that exponential means something like c^n, superlinear is n^c, and linear cn?


What Locke1689 said. If you're not familiar with big O notation, linear is like f(x) = 2x, quadratic is like f(x) = x^2, and exponential is like f(x) = 2^x. There's a huge difference between quadratic and exponential: exponential grows significantly faster as x increases. For computing, the difference is significant. Cobham's thesis says that polynomial algorithms (which includes quadratic) are reasonable to perform, while exponential algorithms aren't.


Superlinear is anything above linear. This includes pseudolinear (e.g., O(nlog n)). Exponential is O(m^n). Linear is O(n).

Edit: And polynomial is O(n^m).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: