As to the language, you are right that in n^2 and n^3, the numbers 2 and 3 are exponents. Your interpretation makes perfect sense, but doesn't match the way the words are used. Those functions are called polynomial functions because in a polynomial, all the exponents are constants (however big they may happen to be). The term exponential is reserved for when the exponent is the variable, which is a much faster-growing kettle of fish.
The Factorial function n! , that counts how many ways you can arrange n objects in a row, grows exponentially:
There's one way to order 1 object: pick it, and you're done. For two, you get two ways to pick the first one, and then there's only one way to pick remaining one. For 3 object, there are 3 ways to pick the first, multiplied by two ways to pick the remaining two, and so on.
Here's the first 10 values:
1 2 6 24 120 720 5040 40320 362880 3628800
This terminology issue has been bugging me for two years, because of the pandemic. It makes me crazy to know that most people, and many of our leaders, have no idea of what an epidemiologist means when he talks about exponential growth. The ones who think they know are probably thinking about polynomial growth -- already scary, but still nothing on exponential. It's just really hard to understand how fast it is.
And you're right that I wasn't so clear about what has to be different and what the same, and your understanding is good. The point I wanted to make is that if there are hidden loops then you have two variables, but one is easy to forget about (often hidden inside some library routine). If the number of times through the loop is the same, you're surely in n^2-land... But you don't have to have n*n in such an obvious way to get O(n^2) growth:
for (i = 0; i < n; i++) {
for (j = 0; j < i; i++) {
i_do_a_lot_of this(i, j);
}
}
As long as the limits on the nested loops grow together, you can still get a quadratic time. Loops that build data up can do this really easily if the inner loop depends on the size of the data being built.
On the original Macs the system's function to add a menu item to a menu was pretty obvious. It scanned down the menu to the end, then added a new item. When this met Microsoft Word, the result was that graphic designers and font-freaks would have to wait over a minute for Word to start up, because it was adding all the fonts in the system to the font menu one at time. For 10 fonts that was 45 loops. For 100 fonts that's 4950 loops, for 120 it's over 7000. Of course, you if passed the whole list at one time, it just copied all the items, and even on those old machines you could have 100's or thousands of items (if you wanted to).
So for a working programmer, it really helps to be aware of O(n^2) as the start of bad growth -- sometimes it is best that can be done, but then you'll only want to use if you know the sizes are really limited. Otherwise, it may well involve long runtimes and "big computing" to get the answer.
There are some quadratic implementations that do make it into interfaces. Breaking lines for a paragraph or an editor are often implemented in a quadratic way (you can avoid the slowdown, but it's real data structure work), so you often see text editors become painfully slow if a very large file has only one line in it. Megabyte long lines aren't part of the design point of code editors, and the unreasonable slowness with lines of thousands of characters is not worth fixing.
As to the language, you are right that in n^2 and n^3, the numbers 2 and 3 are exponents. Your interpretation makes perfect sense, but doesn't match the way the words are used. Those functions are called polynomial functions because in a polynomial, all the exponents are constants (however big they may happen to be). The term exponential is reserved for when the exponent is the variable, which is a much faster-growing kettle of fish.
The Factorial function n! , that counts how many ways you can arrange n objects in a row, grows exponentially:
There's one way to order 1 object: pick it, and you're done. For two, you get two ways to pick the first one, and then there's only one way to pick remaining one. For 3 object, there are 3 ways to pick the first, multiplied by two ways to pick the remaining two, and so on.
Here's the first 10 values:
This terminology issue has been bugging me for two years, because of the pandemic. It makes me crazy to know that most people, and many of our leaders, have no idea of what an epidemiologist means when he talks about exponential growth. The ones who think they know are probably thinking about polynomial growth -- already scary, but still nothing on exponential. It's just really hard to understand how fast it is.
And you're right that I wasn't so clear about what has to be different and what the same, and your understanding is good. The point I wanted to make is that if there are hidden loops then you have two variables, but one is easy to forget about (often hidden inside some library routine). If the number of times through the loop is the same, you're surely in n^2-land... But you don't have to have n*n in such an obvious way to get O(n^2) growth:
As long as the limits on the nested loops grow together, you can still get a quadratic time. Loops that build data up can do this really easily if the inner loop depends on the size of the data being built.
On the original Macs the system's function to add a menu item to a menu was pretty obvious. It scanned down the menu to the end, then added a new item. When this met Microsoft Word, the result was that graphic designers and font-freaks would have to wait over a minute for Word to start up, because it was adding all the fonts in the system to the font menu one at time. For 10 fonts that was 45 loops. For 100 fonts that's 4950 loops, for 120 it's over 7000. Of course, you if passed the whole list at one time, it just copied all the items, and even on those old machines you could have 100's or thousands of items (if you wanted to).
So for a working programmer, it really helps to be aware of O(n^2) as the start of bad growth -- sometimes it is best that can be done, but then you'll only want to use if you know the sizes are really limited. Otherwise, it may well involve long runtimes and "big computing" to get the answer.
There are some quadratic implementations that do make it into interfaces. Breaking lines for a paragraph or an editor are often implemented in a quadratic way (you can avoid the slowdown, but it's real data structure work), so you often see text editors become painfully slow if a very large file has only one line in it. Megabyte long lines aren't part of the design point of code editors, and the unreasonable slowness with lines of thousands of characters is not worth fixing.
This is great info and I sincerely appreciate you taking the time to spell this out so clearly. Always learning... Thank you!