4 ms·

Big O is important. I actually have to frequently understand whether my function runs in logarithmic or linear or quadratic or exponential time relative to some

Big O is important. I actually have to frequently understand whether my function runs in logarithmic or linear or quadratic or exponential time relative to some value. I can see an issue if you’re asking for a weird big O which really isn’t useful in practice, like “oh, we were expecting this weird algorithm which is O(log log n), not something O(log n)”, or having to calculate the big O of one of those weird algorithms.

camgunz 5y ago
It's important but like, it generally boils down to "do you have nested loops" and "are you using a binary tree". A lot of system behavior isn't defined by these kinds of decisions because your N is small. Rather, it's defined by say TCP backoffs or queue sizes, or the broad architecture of the system (must you wait for consensus, do you use Salesforce SObjects as a cache before dumping into Postgres--a real life example--what is your "needs rerendering" trigger). I think it's useful for a programmer to have this kind of basic knowledge of code, but the amount of play it gets in interviews is pretty disproportionate to its importance.
- dominotw 5y ago
  what about db table scan vs index. that happens all the time.
  - camgunz 5y ago
    I guess this is more of a "do you know about database indexes" question, but I think if it less of a gotcha and more of a jumping off point into a discussion you can take it in a number of directions: - time vs. space tradeoffs - insert vs. select tradeoffs - Oh yeah they're binary trees also, with those implications - What's reasonably distributable (downsides of UUIDs) - at what point might you have query performance issues you can address w/ indexes But like, again practically speaking I think this is just an experience test question. I think I'd prefer something like "on your resume you have Postgres experience dating back 7 years, tell me what you think about it, what its strengths and weaknesses are, and why you would or wouldn't use it". --- Maybe you have thoughts about this too, but I'm also starting to develop some thoughts around whether to consider interviews quizzes/tests or conversations. Thinking about it, I've always approached my interviews (on both sides of the table) as conversations--even questions with simple answers. I guess that's why my answer here is "this should be a discussion about databases" and less "table scans vs. index scans in 30 seconds go". It's totally OK to drill down into specifics and be technical, but this is potentially your first interaction with a new colleague, and you should be collegial, not domineering and inscrutable right? I think we get so worried about hiring a faker that we justify anything to avoid it.
jameshart 5y ago
The emphasis placed on big-O in interviews is weird though. Accidentally quadratic code happens, sure, but the way the industry uses it as an interviewing shibboleth makes it feel like this is a safety critical issue; as if at some point a developer used an O(n log n) algorithm when an O(n) algorithm existed and people died. Complexity can be insidious, and it can lead to annoying bugs you only discover in pathological data cases, but it is in no way as important in software development as correctness. Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. Your O(log n) recursive tree traversal is beautifully efficient. Too bad it stack overflows with trivial tree depths.
- rdw 5y ago
  > Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. In my experience, these are not actually that different. Even in straightforward web development on smallish data sets, it's pretty easy to write something that runs "fast on my machine" but is so slow on production-sized data that it is effectively infinite.
  - jameshart 5y ago
    Yes, as I say, clearly it happens. But when it does the results are no worse than any other bug. And it’s far more common, and more dangerous, in my experience, to see a loop that assumes it must eventually reach a terminal condition that isn’t actually guaranteed. I just don’t think the risk of hiring someone who misestimates the time complexity of an algorithm is sufficiently great that it’s worth explicitly filtering for. Why is this the one piece of hard won experience or academic knowledge that we need a candidate to have before they join our company, given that it’s something that can be taught in a single CS101 lecture, and in practical terms, something I can explain to a competent developer in about ten minutes?
- ryandrake 5y ago
  Even weirder: A lot of companies who are obsessed with big-O and algorithm complexity don't ask candidates even basic questions that require them to think across many orders of magnitude, in terms of time and storage. I'd argue that being flexible enough and able to visualize things across, say, ten orders of magnitude, is a more critical programming skill than knowing big-O. Even basic questions: Answer with either the word nanoseconds, microseconds, or milliseconds: What's the order-of-magnitude latency of CPU cache lookup? Reading 1MB from spinning disk? Reading 1MB from memory? A round trip packet to a server 1km away? A GPU clearing a 4K screen? A mutex lock? Answer with kilobytes, megabytes, or gigabytes: What's the order-of-magnitude size of a digitized photo? A song? A movie? A graphics frame buffer? Wikipedia? Google's homepage? A typical bootloader? A Windows app executable file? A typical CPU L1 cache? L2 cache? Too many junior developers can only answer a few of these, even with the answers having three orders of magnitude granularity! But we constantly ask them to belt out the best and worst case big-O complexity of a binary tree.
PheonixPharts 5y ago
Big O, by definition, assumes as n -> ∞. This can be a really poor assumption in real world software that can bite both ways. Some "expensive" algorithms in terms of big O terms can be pretty efficient given real world data sizes. Additionally that C term that drops off at infinity can matter quite a lot if your real world problem size is small (meaning theoretically efficient algorithms can have a very high upfront cost). Reasoning about actual runtime performance is far more important and intersects with the interesting/useful parts of computational complexity theory. Besides, in every interview I've been in they don't really mean "Big O", because I've never been required to produce a recurrence equation proving it, nor have I been confident the interviewer would even understand such an answer. Understanding performance is hugely important in real world software, but Big O is a tiny part of that in practice.
- charcircuit 5y ago
  You don't need a recurrence relation to prove it. You can use a simple algebra where you are able to combine the complexing of algorithms. For example an O(n) algorithm followed by an O(n^2) algorithm will be O(n^2). In an interview I describe how the complexity of these simpler algorithms get combined into my final answer. I assume that the interviewer and I can agree on some basic stuff like looping over an array is O(n), inserting into a heap is O(log(n)), etc.

camgunz 5y ago

It's important but like, it generally boils down to "do you have nested loops" and "are you using a binary tree". A lot of system behavior isn't defined by these kinds of decisions because your N is small. Rather, it's defined by say TCP backoffs or queue sizes, or the broad architecture of the system (must you wait for consensus, do you use Salesforce SObjects as a cache before dumping into Postgres--a real life example--what is your "needs rerendering" trigger). I think it's useful for a programmer to have this kind of basic knowledge of code, but the amount of play it gets in interviews is pretty disproportionate to its importance.

dominotw 5y ago
what about db table scan vs index. that happens all the time.
- camgunz 5y ago
  I guess this is more of a "do you know about database indexes" question, but I think if it less of a gotcha and more of a jumping off point into a discussion you can take it in a number of directions: - time vs. space tradeoffs - insert vs. select tradeoffs - Oh yeah they're binary trees also, with those implications - What's reasonably distributable (downsides of UUIDs) - at what point might you have query performance issues you can address w/ indexes But like, again practically speaking I think this is just an experience test question. I think I'd prefer something like "on your resume you have Postgres experience dating back 7 years, tell me what you think about it, what its strengths and weaknesses are, and why you would or wouldn't use it". --- Maybe you have thoughts about this too, but I'm also starting to develop some thoughts around whether to consider interviews quizzes/tests or conversations. Thinking about it, I've always approached my interviews (on both sides of the table) as conversations--even questions with simple answers. I guess that's why my answer here is "this should be a discussion about databases" and less "table scans vs. index scans in 30 seconds go". It's totally OK to drill down into specifics and be technical, but this is potentially your first interaction with a new colleague, and you should be collegial, not domineering and inscrutable right? I think we get so worried about hiring a faker that we justify anything to avoid it.

jameshart 5y ago

The emphasis placed on big-O in interviews is weird though. Accidentally quadratic code happens, sure, but the way the industry uses it as an interviewing shibboleth makes it feel like this is a safety critical issue; as if at some point a developer used an O(n log n) algorithm when an O(n) algorithm existed and people died. Complexity can be insidious, and it can lead to annoying bugs you only discover in pathological data cases, but it is in no way as important in software development as correctness. Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. Your O(log n) recursive tree traversal is beautifully efficient. Too bad it stack overflows with trivial tree depths.

rdw 5y ago
> Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. In my experience, these are not actually that different. Even in straightforward web development on smallish data sets, it's pretty easy to write something that runs "fast on my machine" but is so slow on production-sized data that it is effectively infinite.
- jameshart 5y ago
  Yes, as I say, clearly it happens. But when it does the results are no worse than any other bug. And it’s far more common, and more dangerous, in my experience, to see a loop that assumes it must eventually reach a terminal condition that isn’t actually guaranteed. I just don’t think the risk of hiring someone who misestimates the time complexity of an algorithm is sufficiently great that it’s worth explicitly filtering for. Why is this the one piece of hard won experience or academic knowledge that we need a candidate to have before they join our company, given that it’s something that can be taught in a single CS101 lecture, and in practical terms, something I can explain to a competent developer in about ten minutes?
ryandrake 5y ago
Even weirder: A lot of companies who are obsessed with big-O and algorithm complexity don't ask candidates even basic questions that require them to think across many orders of magnitude, in terms of time and storage. I'd argue that being flexible enough and able to visualize things across, say, ten orders of magnitude, is a more critical programming skill than knowing big-O. Even basic questions: Answer with either the word nanoseconds, microseconds, or milliseconds: What's the order-of-magnitude latency of CPU cache lookup? Reading 1MB from spinning disk? Reading 1MB from memory? A round trip packet to a server 1km away? A GPU clearing a 4K screen? A mutex lock? Answer with kilobytes, megabytes, or gigabytes: What's the order-of-magnitude size of a digitized photo? A song? A movie? A graphics frame buffer? Wikipedia? Google's homepage? A typical bootloader? A Windows app executable file? A typical CPU L1 cache? L2 cache? Too many junior developers can only answer a few of these, even with the answers having three orders of magnitude granularity! But we constantly ask them to belt out the best and worst case big-O complexity of a binary tree.

PheonixPharts 5y ago

Big O, by definition, assumes as n -> ∞. This can be a really poor assumption in real world software that can bite both ways. Some "expensive" algorithms in terms of big O terms can be pretty efficient given real world data sizes. Additionally that C term that drops off at infinity can matter quite a lot if your real world problem size is small (meaning theoretically efficient algorithms can have a very high upfront cost). Reasoning about actual runtime performance is far more important and intersects with the interesting/useful parts of computational complexity theory. Besides, in every interview I've been in they don't really mean "Big O", because I've never been required to produce a recurrence equation proving it, nor have I been confident the interviewer would even understand such an answer. Understanding performance is hugely important in real world software, but Big O is a tiny part of that in practice.

charcircuit 5y ago
You don't need a recurrence relation to prove it. You can use a simple algebra where you are able to combine the complexing of algorithms. For example an O(n) algorithm followed by an O(n^2) algorithm will be O(n^2). In an interview I describe how the complexity of these simpler algorithms get combined into my final answer. I assume that the interviewer and I can agree on some basic stuff like looping over an array is O(n), inserting into a heap is O(log(n)), etc.