3 ms·

I actually learned about Big O from a friend with a computer science background (I don't have one) when I was working on some jQuery show/hide code a few years

I actually learned about Big O from a friend with a computer science background (I don't have one) when I was working on some jQuery show/hide code a few years ago. The idea was: you have a bunch of products on a page, and as you check and uncheck features you want, only the products matching your criteria are shown. Originally, my logic was something like "for each checkbox that's checked or unchecked.... for each product that may or may not have that feature..." The nested for loop was fine with a small number of checkboxes and products, but as I got more products and more checkboxes, it began to slow down. My friend pointed out that it was Big O of N squared and explained what that meant. It was eye-opening. I rewrote it to first compile a list of checked features (one pass through the checkboxes) and then show/hide the products (one pass through the products), which scales linearly. I can't say that I think about Big O every time I write an algorithm, but I do have a sense that nested loops are dangerous.

Shenglong 15y ago
How many checkboxes were there, that you actually noticed the delay in a N^2?
- billybob 15y ago
  Maybe 8 checkboxes, but hundreds of products.
- ww520 15y ago
  O(N^2) can cause slowdown very fast. 1000^2 is a million operations. 10000^2 is 100 million operations. If each operation is 100 instructions, that's 10Ghz very roughly. That would cause pauses even with a modern CPU.
jmreardon 15y ago
Big O notation is intended to convey the algorithm's runtime as a function of the inputs. By the sounds of it, the number of checkboxes you had was actually fixed and relatively small. In this case, the algorithm is still O(n). The real problem with your code is that you went through the list (an expensive operation) multiple times. This gives you a large constant factor, not O(n^2). Because Big O notation is only concerned with large (asymptotic) values, the constants are generally ignored. If you had a form where the number of checkboxes scaled with the number of items on the list, then you might end up with an O(n^2) algorithm, depending on how exactly they scale.
- billybob 15y ago
  You're right - it wasn't O(n^2); the number of operations was (Number of checkboxes) x (Number of products). So with 10 checkboxes and 200 products, I had 2000 operations. 201 products = 2010 operations. My problem would have been N^N if I had been doing "for every checkbox... for every checkbox" instead of "for every checkbox... for every product..." So it wasn't n^2, but it was scaling poorly. The way I rewrote it, I had (Number of products) operations. So for 200 products, I had 200 operations. You can see that this made it much more tenable to add 100 more products, even if it wasn't N^2.

Shenglong 15y ago

How many checkboxes were there, that you actually noticed the delay in a N^2?

billybob 15y ago
Maybe 8 checkboxes, but hundreds of products.
ww520 15y ago
O(N^2) can cause slowdown very fast. 1000^2 is a million operations. 10000^2 is 100 million operations. If each operation is 100 instructions, that's 10Ghz very roughly. That would cause pauses even with a modern CPU.

jmreardon 15y ago

Big O notation is intended to convey the algorithm's runtime as a function of the inputs. By the sounds of it, the number of checkboxes you had was actually fixed and relatively small. In this case, the algorithm is still O(n). The real problem with your code is that you went through the list (an expensive operation) multiple times. This gives you a large constant factor, not O(n^2). Because Big O notation is only concerned with large (asymptotic) values, the constants are generally ignored. If you had a form where the number of checkboxes scaled with the number of items on the list, then you might end up with an O(n^2) algorithm, depending on how exactly they scale.

billybob 15y ago
You're right - it wasn't O(n^2); the number of operations was (Number of checkboxes) x (Number of products). So with 10 checkboxes and 200 products, I had 2000 operations. 201 products = 2010 operations. My problem would have been N^N if I had been doing "for every checkbox... for every checkbox" instead of "for every checkbox... for every product..." So it wasn't n^2, but it was scaling poorly. The way I rewrote it, I had (Number of products) operations. So for 200 products, I had 200 operations. You can see that this made it much more tenable to add 100 more products, even if it wasn't N^2.