Ask HN: When was the last time you used big-o in a web app?

I can't tell you what they are, because they are all projects that might soon be opened, and while they're not exactly in stealth mode, they are good ideas that I can only work on slowly. I need to get enough of an advantage to be able to stay ahead of those with more web implementation experience.

However, one involves analysing the cross-connections between hundreds of users, and hundreds of small units of data they each have. The naive algorithm is O(n^3 m^2) and is too slow for more than 30 users or 100 units of data. The analysis showed that early, so the architecture of the system was changed to cause the data to "flow" around the system and agregate closer to where it was needed.

Another application uses proximity detection on potentially thousands of points. Again, the naive algorithm worked for small numbers of users (I use the term loosely - they're more "agents" than users), and again, big-O analysis showed the critical points in the system.

I'm sure that most web development consists of gluing libraries together, stuffing databases, and populating forms or similar. Interesting stuff that I do uses algorithmic analyses.

So I always track my O()s, even if it doesn't boil down to a rigorous analysis.

The real value of Bio-O isn't knowing how to prove that red-black trees have O(1) amortized insert but rather understanding the tools used and the code written better.

If something is O(N^2) or worse, it "doesn't scale" and you won't usually see it done in a web app. That is, there's a whole shadow universe of web apps that you've never seen because the resource demands are too high.

I agree with the folks who mentioned doing a sort of naive, intuitive "big O" analysis as you work, as opposed to a formal analysis. I was recently working on some social graph stuff, and I started down the path of doing an "all pairs shortest paths" determination with Floyd-Warshall (which is O(|V|^3) complexity).. needless to say, it only took a few minutes to realize that this won't work for any real world size datasets and would require a different approach. If nothing else, you quickly find that the naive approach doesn't work for any meaningful amount of data, as just building an adjacency matrix for a few hundred entries, if the datatype is an int (which is what I was using at the time) will blow past the heap size limit on a 32bit JVM.

I'm actually still researching and considering exactly what I'm going to do. I don't necessarily need every shortest path in the system, so the first cut at optimizing this will probably be to cook up something that only calculates a portion of the paths. Another approach might be to look into a parallelized algorithm that can do this on a cluster. Beyond that, I've been poking around trying to see if there's a way to apply a sort of incremental evaluation approach to the problem, where I build the initial matrix of path distances, and then incrementally recompute just the part I care about, when something changes.

Anyway, at the moment, this is the largest extent to which I've actually had to spend some time thinking about the kind of stuff that I studied in some of my CS classes... I've actually got all my algorithms books of the shelf, and digging in, as I research this. :-)

Because of the scale of data I'm using, I'm acutely aware of big-O. I guess what's most interesting is that gcc is able to take some of those "slow" operations and make them super fast (if it can fit them in a register) and other times I get the full O(n) effect. Valgrind has been a very useful tool, and can empirically show you where your program is going to blow up (if you doubt your big-O analysis).

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.

Last time I really had to consider big O in a web app was 2009. Of course, it had nothing to do with the fact that it was a web app and not desktop or otherwise. It had everything to do with the problem I was trying to solve.

At all times when writing software the engineer should know a) the complexity of the code they are trying to write and b) what the memory complexity of the program is and, in many cases (slightly off-topic), c) the approximate times it takes to do certain simple tasks (this may be memory access, simple disk/network IO, database queries etc)

This is useful because it protects you from writing programs that "perform" unexpectedly badly (I'm confused why anyone would expect them to "perform" without thinking about it).

It may sound like a lot of work, but thankfully most things you program are really constructed of simpler things that have well known complexities (simple loops, sorting, hashing, stuff like that)

At our company (pretty straight-forward social web-app), we have surprisingly many pieces of code where the trivial implementation wouldn't work. We have a graph of different users and relations and want to maintain a transitive closure for each type of edge while also maintaining a bunch of indexes.

Even on the client side we have simple things, such as an autocomplete box for usernames. With many users, we can't just keep an array of all existing users and iterate through it on every keystroke. At that point you have so many options to choose from (e.g. have an index on the server and do a request for the filtered list after short timeout or build a simple index (searchtree) on the client and use that for searching) and you couldn't make a decision without knowing about runtime complexity, constant time factors and memory usage.

The most memorable big O analysis that actually led to fixing a performance bug was when I wrote the caching layer of a file system using bubble sort for sorting the dirty blocks before flushing. It slowed down noticeably, like seconds of pause with 100% CPU, when the cache size exceeded 10K blocks. Replacing it with heap sort made the problem go away. O(nlogn) really is much more scalable than O(n^2).

If you mean using your knowledge of computational complexity to inform your choice of algorithms and data structures, then all the freaking time.

A standard tableview (static row heights) is laid out in constant time, whereas using variable row heights is laid out in logarithmic time.

An early implementation provided variable row heights in linear time (or perhaps n^2, I don't recall)... this caused scrolling to be absolutely terrible and unusable if you had more than a couple dozen rows.

With constant time we can, theoretically, have any number of rows in your tableview and it will remain just as performant as if you only had 1.

If you're building real software and throw out the concept of time complexity, then you're setting yourself up for failure in the long run.