Hacker Newsnew | comments | ask | jobs | submitlogin
benhoyt 327 days ago | link | parent

Yes, regularly. I'm a backend web developer who works on a fairly large-scale website, and program mostly in Python. It's pretty important to know that code like this (which we have in our photo search code):

   for image in images:
       if image.hotel_id in hotel_ids:
           ...
will be O(N) if hotel_ids is a set or dict (with O(1) lookup), but O(N²) if hotel_ids is a list (with O(N) lookup). We're not talking about micro-optimizations here -- when N is of moderate size, it can mean the differences in render time between 30 milliseconds and 3 seconds.

When developers don't have a feel for this, it really slows them down -- both figuratively and literally.

FYI, I wrote a blog entry about how our photo search engine works here: http://tech.oyster.com/how-our-photo-search-engine-really-wo...



Joeboy 327 days ago | link

> When developers don't have a feel for this, it really slows them down -- both figuratively and literally.

Of course, I'm just not clear how Big-O helps with that. To me, the required insights seem to be:

* Things are slower when the computer has to do more work

* A feel for what strategies result in the computer doing more work

I can't think of many cases when saying "This algorithm is O(N^2)" is significantly more useful than saying "This algorithm is going to be really slow".

-----

mseebach 327 days ago | link

It's like grammar: You don't sit around articulating "this is the subject, this is the object, and I need the third person singular over there" when you write - but knowing the mechanics of grammar allows you to write texts with correct grammar more or less intuitively, and it's easy to reach back and pull out a rule when you think something sounds weird.

-----

zorked 327 days ago | link

At least where I work the definition of slow does not cross complexity boundaries. A O(n) algorithm that takes 100 seconds to run is "slow" compared to a O(n) algorithm that takes 50 seconds to run. But if it crosses a complexity boundary and it's now, O(n^2), we state that instead of saying it's "slow", because often it's far more tragical than just taking a little extra time to run.

-----

kryptiskt 327 days ago | link

> I can't think of many cases when saying "This algorithm is O(N^2)" is significantly more useful than saying "This algorithm is going to be really slow".

But to know that it will be slow you have to know how it scales with the input size. Because the list example may work just fine when the website has little data (oftentimes an O(N^2)-algorithm may even be faster than an O(N)-algorithm on small data) and hit you when you scale up. And the O-notation gives you a tool to estimate how the work scales. Any alternative to the O-notation is either more complex (look up Analytic Combinatorics http://ac.cs.princeton.edu/home/) or just an informal treatment of O-notation.

-----

jstanley 327 days ago | link

But how can you know how slow it is going to be under a production workload? Is very useful to be able to time some code on a small input set, then extrapolate based on knowledge of time complexity to find out roughly how long the full input will take. If you don't know the time complexity, this is impossible.

-----

Joeboy 327 days ago | link

> But how can you know how slow it is going to be under a production workload?

In a web dev context, load testing. I appreciate that that's not so easy if your program takes a week to run.

> Is very useful to be able to time some code on a small input set, then extrapolate based on knowledge of time complexity to find out roughly how long the full input will take. If you don't know the time complexity, this is impossible.

I suppose my confusion is that with code I've written, I think I generally understand the time complexity without having to use Big-O notation. I can sort of see that there are times you might want to tell a colleague something like "careful, this code I wrote is O(n^3)", but I'm wondering what kind of job entails doing that on a regular basis.

-----




Lists | RSS | Bookmarklet | Guidelines | FAQ | DMCA | News News | Feature Requests | Bugs | Y Combinator | Apply | Library

Search: