4 ms·

This same effect occurs in computer science with "big-O notation" Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of

This same effect occurs in computer science with "big-O notation" Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of the notation, rather than demonstrate how to use the resulting insight to make the code better. Just because I don't know the formal rules of how to calculate Big-O they assume I can't write any code that scales. Its like a teacher assuming a student can't speak english because he can't recite the adjective order chart from memory.

wpietri 11y ago
Yep. I don't deny that academic success is correlated with real-world success, but assuming that they're identical is a terrible mistake. Especially now given how hard it is to hire good developers, I think Mensa-puzzle interviews and CS-exam interviews are terribly wasteful. In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.
east2west 11y ago
Since big-O and other asymptotic notations come from calculus I don't think it is a bad idea to know precise definition. For programmers it is questionable how useful they are in everyday job and I would just forgo asking them during interviews, although I have been asked in recent interviews. These asymptotic notations are immensely helpful in finite approximation of continuous functions using infinite series like Taylor series or orthogonal polynomials. Computer scientists borrowed the notations and abused them as if they were the final arbitrator of things when they are not; Knuth noted too much game is being played with them in academic publication. Further attempts at drawing analogies different kinds of convergence and growth functions have not found widespread use. I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.
gohrt 11y ago
Wow, I have never interviewed at a company that asked for formal rules of big-O. And of course most professionals at those same companies (you've heard of them) tend to use "O()" to mean "approximately" or "on the order of", as in "O(1000)"
mason55 11y ago
I don't think it's necessary to know the formal definition of big O (or big Theta or big Omega) but there's a spectrum there. If all you can say is "nested for loops are bad" and you can't explain why hash tables provide fast lookups then I'm not going to be very impressed. On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.
- TeMPOraL 11y ago
  I'm going to render myself permanently unemployable in the industry by admitting this, but one thing I'm still not really sure about is why every text on CS assumes array have O(1) access? I mean, in the real world it surely takes more time to reach elements further in memory, if only because electrons travel at finite speeds and also you can't magically write any number into a register, there has to be a piece of electronics that will count up to it somehow. Is it only because all those hardware operations are so stupidly fast we don't care about them day-to-day usage, or is there another reason for assuming arrays have O(1) access?
  - xKingfisher 11y ago
    My understanding from my algorithms class is that it is simply a matter of choosing your abstraction. Big O is meant to provide a general framework for qualifying and comparing algorithms free of machine dependent factors like execution time. It is not possible to account for every possible facet of every operation so some operations are chosen to be O(1) even though in reality they take multiple machine code instructions or have slightly varying real world performance. Saying array access is O(1) also does not account for different architectures or cache misses, which have major performance implications. So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation. Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level. Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1). This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.
mzs 11y ago
Just as in math there is an applied and theoretical aspect, there is in CS as well. There are plenty of great opportunities to us calculus in stat, econ, physics and so on, but calculus can be a great introduction to proof writing itself. In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say. The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.

wpietri 11y ago

Yep. I don't deny that academic success is correlated with real-world success, but assuming that they're identical is a terrible mistake. Especially now given how hard it is to hire good developers, I think Mensa-puzzle interviews and CS-exam interviews are terribly wasteful. In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.

east2west 11y ago

Since big-O and other asymptotic notations come from calculus I don't think it is a bad idea to know precise definition. For programmers it is questionable how useful they are in everyday job and I would just forgo asking them during interviews, although I have been asked in recent interviews. These asymptotic notations are immensely helpful in finite approximation of continuous functions using infinite series like Taylor series or orthogonal polynomials. Computer scientists borrowed the notations and abused them as if they were the final arbitrator of things when they are not; Knuth noted too much game is being played with them in academic publication. Further attempts at drawing analogies different kinds of convergence and growth functions have not found widespread use. I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.

gohrt 11y ago

Wow, I have never interviewed at a company that asked for formal rules of big-O. And of course most professionals at those same companies (you've heard of them) tend to use "O()" to mean "approximately" or "on the order of", as in "O(1000)"

mason55 11y ago

I don't think it's necessary to know the formal definition of big O (or big Theta or big Omega) but there's a spectrum there. If all you can say is "nested for loops are bad" and you can't explain why hash tables provide fast lookups then I'm not going to be very impressed. On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.

TeMPOraL 11y ago
I'm going to render myself permanently unemployable in the industry by admitting this, but one thing I'm still not really sure about is why every text on CS assumes array have O(1) access? I mean, in the real world it surely takes more time to reach elements further in memory, if only because electrons travel at finite speeds and also you can't magically write any number into a register, there has to be a piece of electronics that will count up to it somehow. Is it only because all those hardware operations are so stupidly fast we don't care about them day-to-day usage, or is there another reason for assuming arrays have O(1) access?
- xKingfisher 11y ago
  My understanding from my algorithms class is that it is simply a matter of choosing your abstraction. Big O is meant to provide a general framework for qualifying and comparing algorithms free of machine dependent factors like execution time. It is not possible to account for every possible facet of every operation so some operations are chosen to be O(1) even though in reality they take multiple machine code instructions or have slightly varying real world performance. Saying array access is O(1) also does not account for different architectures or cache misses, which have major performance implications. So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation. Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level. Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1). This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.

mzs 11y ago

Just as in math there is an applied and theoretical aspect, there is in CS as well. There are plenty of great opportunities to us calculus in stat, econ, physics and so on, but calculus can be a great introduction to proof writing itself. In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say. The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.