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

He might be using "exponential" to mean "superlinear", which seems to be the sense a lot of my students try to use it in (as well as non-technical people).


Now that you mention it, I guess non-technical people do tend to use that definition. I had never thought about it before. It's unfortunate, considering there's a big difference between, say, quadratic and exponential growth. In fact, it tends to be a more impactful difference than between linear and quadratic, especially regarding algorithms.


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: