Re:Ask HN: When was the last time you used big-o in a web app?
by jmreardon on Tuesday August 02, 2011 @01:14PM
(#2837864)
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.
Re:Ask HN: When was the last time you used big-o in a web app?
by billybob on Wednesday August 03, 2011 @09:03AM
(#2840952)
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.
Re:Ask HN: When was the last time you used big-o in a web app?
by Shenglong on Tuesday August 02, 2011 @12:34PM
(#2837712)
How many checkboxes were there, that you actually noticed the delay in a N^2?
Re:Ask HN: When was the last time you used big-o in a web app?
by ww520 on Tuesday August 02, 2011 @01:38PM
(#2837965)
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.
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.