5 ms·

So, I see where you are coming from (I actually love academic CS). But the VAST majority of the programming work out there does not require any Big-O analysis.

by ammon 11y ago

So, I see where you are coming from (I actually love academic CS). But the VAST majority of the programming work out there does not require any Big-O analysis. It just does not. It's used as a tool in interviews to (essentially) look for rigor. The problem is that this harms people who are rigorous as hell in low-level details of JS and V8 (something I'd posit is actually more useful to many more companies), but never studied academic CS. There's nothing wrong with valuing the skill of complexity analysis. But there's a mismatch in how common it is to look for this.

markeroon 11y ago
If someone else is well versed in complexity then it's fine to hire a js person with no knowledge of it. If you're expecting the candidate to produce performant code, they may need said knowledge.
aidenn0 11y ago
I have more than once in my professional career run into programmers who tested on small inputs and assumed the timing would scale at least close to linearly.
- ammon 11y ago
  Fair point. But is it not much more common to encounter a programer who cannot break a complex system into loosely coupled components? Or who does not use consistent naming conventions? Or who is smart but lazy? I'd rate all of these as equally important things to try to evaluate in an interview. I am a strong believer in looking for strength in an interview. Someone really rocking complexity analysis is a strong positive (shows that they are smart and pedantic in a good way). But so does clean, smart code and great loose coupling.
  - aidenn0 11y ago
    Oh, I'd never disqualify an interviewee purely for not knowing this stuff, but it is useful to know. [edit] Also, I care far less about whether they can solve some problem on paper about asymptotic complexity than if they have some sense of what it means. Someone with little formal training who discovered the classic python "Add to the end of string" algorithm is N^2 and figured out a working knowledge of N^2 vs. N is better than someone who memorized a bunch of math but can't apply it because it went in the "math box"[1] 1: http://zenoferox.blogspot.com/2009/10/deep-inside-math-box.html http://zenoferox.blogspot.com/2009/10/deep-inside-math-box.h...
- davorb 11y ago
  There are a lot of situations where a "worse" algorithm will be significantly faster that another algorithm that's faster in theory, due to memory locality. In practice, it is very hard to know beforehand what parts of your program will scale and what parts won't.
  - aidenn0 11y ago
    This is categorically untrue if you are talking about large numbers and asymptotic complexity. It is true that algorithms with a constant factor larger number of operations may have such properties, but O(n) will always beat O(n^2) eventually, and in nearly all real-world cases at a fairly small n (1000 L1 cache accesses is slower than 1 memory access so n=1000 will be enough to counter any locality issues).
quanticle 11y ago
But the VAST majority of the programming work out there does not require any Big-O analysis. Your point is simultaneously valid and irrelevant. The vast majority of programming doesn't involve any Big-O analysis. But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. To make an analogy with driving: the vast majority of driving doesn't involve parallel parking. But you still need to know parallel parking to pass a driving test.
- nrb 11y ago
  You do not need to know parallel parking to pass a driving test, in Illinois and probably many other states.
- whatshisface 11y ago
  You don't need to know how to prove a big-O to optimize an algorithm. Anyone who can think about what their code is doing will have at least some sense of how much it is doing. Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper.
  - quanticle 11y ago
    Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper. Sure. I've never been asked for a formal mathematical proof of the Big-O complexity of my algorithms in an interview. And, as an interviewer, I've never asked. Intuition is exactly what interviews are looking for. If an algorithm has a nested for loop, and the inner loop is traversing the full data set, you should be able to say, "Oh, yeah, that looks like O(n^2) time complexity." If an algorithm is storing every element of a data-set in memory, you should be able to say, "That's O(n) space complexity." Big-O notation, in practice, is a handy shorthand for talking about various classes of algorithms, and ranking them in order of how much time/space they take.
- 11y ago
jlarocco 11y ago
> But the VAST majority of the programming work out there does not require any Big-O analysis. It just does not. I just don't agree with this. Maybe it's true for people doing strictly front end web development (i.e. pure HTML and CSS), but basic algorithm analysis comes up all the time when writing any kind of real code. I think your attitude is actually part of the reason software sucks so bad nowadays. People act like efficiency doesn't matter at all and Big-O is useless and then turn around and act surprised when browsing a website causes Firefox to use 800 Mb of RAM, or their top of the line server only handles 50 connections a second. There's a connection there.
deleted 11y ago
[deleted]

by ammon 11y ago

markeroon 11y ago

If someone else is well versed in complexity then it's fine to hire a js person with no knowledge of it. If you're expecting the candidate to produce performant code, they may need said knowledge.

aidenn0 11y ago

I have more than once in my professional career run into programmers who tested on small inputs and assumed the timing would scale at least close to linearly.

ammon 11y ago
Fair point. But is it not much more common to encounter a programer who cannot break a complex system into loosely coupled components? Or who does not use consistent naming conventions? Or who is smart but lazy? I'd rate all of these as equally important things to try to evaluate in an interview. I am a strong believer in looking for strength in an interview. Someone really rocking complexity analysis is a strong positive (shows that they are smart and pedantic in a good way). But so does clean, smart code and great loose coupling.
- aidenn0 11y ago
  Oh, I'd never disqualify an interviewee purely for not knowing this stuff, but it is useful to know. [edit] Also, I care far less about whether they can solve some problem on paper about asymptotic complexity than if they have some sense of what it means. Someone with little formal training who discovered the classic python "Add to the end of string" algorithm is N^2 and figured out a working knowledge of N^2 vs. N is better than someone who memorized a bunch of math but can't apply it because it went in the "math box"[1] 1: http://zenoferox.blogspot.com/2009/10/deep-inside-math-box.html http://zenoferox.blogspot.com/2009/10/deep-inside-math-box.h...
davorb 11y ago
There are a lot of situations where a "worse" algorithm will be significantly faster that another algorithm that's faster in theory, due to memory locality. In practice, it is very hard to know beforehand what parts of your program will scale and what parts won't.
- aidenn0 11y ago
  This is categorically untrue if you are talking about large numbers and asymptotic complexity. It is true that algorithms with a constant factor larger number of operations may have such properties, but O(n) will always beat O(n^2) eventually, and in nearly all real-world cases at a fairly small n (1000 L1 cache accesses is slower than 1 memory access so n=1000 will be enough to counter any locality issues).

quanticle 11y ago

But the VAST majority of the programming work out there does not require any Big-O analysis. Your point is simultaneously valid and irrelevant. The vast majority of programming doesn't involve any Big-O analysis. But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. To make an analogy with driving: the vast majority of driving doesn't involve parallel parking. But you still need to know parallel parking to pass a driving test.

nrb 11y ago
You do not need to know parallel parking to pass a driving test, in Illinois and probably many other states.
whatshisface 11y ago
You don't need to know how to prove a big-O to optimize an algorithm. Anyone who can think about what their code is doing will have at least some sense of how much it is doing. Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper.
- quanticle 11y ago
  Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper. Sure. I've never been asked for a formal mathematical proof of the Big-O complexity of my algorithms in an interview. And, as an interviewer, I've never asked. Intuition is exactly what interviews are looking for. If an algorithm has a nested for loop, and the inner loop is traversing the full data set, you should be able to say, "Oh, yeah, that looks like O(n^2) time complexity." If an algorithm is storing every element of a data-set in memory, you should be able to say, "That's O(n) space complexity." Big-O notation, in practice, is a handy shorthand for talking about various classes of algorithms, and ranking them in order of how much time/space they take.
11y ago

jlarocco 11y ago

> But the VAST majority of the programming work out there does not require any Big-O analysis. It just does not. I just don't agree with this. Maybe it's true for people doing strictly front end web development (i.e. pure HTML and CSS), but basic algorithm analysis comes up all the time when writing any kind of real code. I think your attitude is actually part of the reason software sucks so bad nowadays. People act like efficiency doesn't matter at all and Big-O is useless and then turn around and act surprised when browsing a website causes Firefox to use 800 Mb of RAM, or their top of the line server only handles 50 connections a second. There's a connection there.

deleted 11y ago

[deleted]