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.
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.
without straining my brain, to me its reasonable to measure complexity by number of interacting components, which is a combination, which is geometric, which is a discrete exponential, right?
Yes but the number of nodes is n, and an "interaction" among m nodes might not be decomposable to a chain of pairwise interactions, which raises the ceiling back to exponetial (actually factorial, which is worse).
What corresponds to interactions that aren't decomposable as pairwise interactions? Race conditions? Resource utilization? Real bugs (and the nastier ones), but probably a minority. So factorial with a relatively small constant in front of it.
But obviously the real answer is to write a program that will correctly verify all other programs.
