Second, you're being gracious in implying that I already know this. I make no qualms about the fact that Big-O is primarily taught in universities - and I'm a self-taught programmer. In fact, I've only recently begun really paying any attention to it at all.
Finally, I have to say that you may have taught me something. (And thank you for that!) I understand that if you have a nested loop, where the inner loop is dependent upon a variable separate from the inner loop, this is quadratic time. But I honestly thought that if both loops were dependent upon the same variable, that this could reliably be referred to as exponential time. After all, if you have a nested loop, and both loops are looping through the same array, you are looping through it a number of times equal to the square of the length of the array. If you were to nest a third loop, where you're once again going through the same array, you would loop through everything a number of times equal to the cube of the length of the array. Of course, "squares" and "cubes" are... exponentials.
But this isn't meant to argue with you in any way. I'll need to read up on it more myself!
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.
First, thank you for the wonderful explanation.
Second, you're being gracious in implying that I already know this. I make no qualms about the fact that Big-O is primarily taught in universities - and I'm a self-taught programmer. In fact, I've only recently begun really paying any attention to it at all.
Finally, I have to say that you may have taught me something. (And thank you for that!) I understand that if you have a nested loop, where the inner loop is dependent upon a variable separate from the inner loop, this is quadratic time. But I honestly thought that if both loops were dependent upon the same variable, that this could reliably be referred to as exponential time. After all, if you have a nested loop, and both loops are looping through the same array, you are looping through it a number of times equal to the square of the length of the array. If you were to nest a third loop, where you're once again going through the same array, you would loop through everything a number of times equal to the cube of the length of the array. Of course, "squares" and "cubes" are... exponentials.
But this isn't meant to argue with you in any way. I'll need to read up on it more myself!
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!