9 ms·

I have no educational training in computer science, but I work as a software developer. I could not answer any of those questions, literally 0 out of 5. 1. Is

I have no educational training in computer science, but I work as a software developer. I could not answer any of those questions, literally 0 out of 5. 1. Is O(2^n) equal to O(3^n)? Why? I have absolutely no idea what that means. But I did have to answer this question: why does the application crash? "Oh...that's because the developer that was pontificating yesterday about how heap operations behave asymptotically forgot to check if the database connection was open before he called the Save method. Apparently, such arcane trivia is beneath him. I can fix it."

Altaco 14y ago
Meanwhile, you discover a long time down the road that the algorithm you thought was fine is actually incredibly slow when scaled to large inputs because you didn't have a good understanding of runtime analysis. Or maybe, as you say, understanding more things makes you worse at coding. Who knows.
- waterlesscloud 14y ago
  I guess I'm not buying that Big-O is a necessary requirement to understand how fast or slow an algorithm will be. It could be that someone understands and uses the process behind it without being at all familiar with the notation.
jrabone 14y ago
Some things you can look up quickly. Being functionally innumerate is not something you can fix with Google. The tedious details of whatever god-forsaken CRUD framework is flavour-of-the-week with the cool kids probably WERE beneath him.
- deleted 14y ago
  [deleted]
radagaisus 14y ago
from all the questions this is the one you MUST know if you want me (or anyone) to trust you with a piece of code. It takes one hour (in wikipedia!) to learn everything you'll need for a day-to-day work complexity assessment with the Big O notation. They asked us this questions on our high school final exams, I'm sure you'll manage.
- mattdeboard 14y ago
  Yeah, I mean, I'm also a self-taught, workaday programmer, and I agree with you. Understanding time complexity to a degree that you can communicate about it isn't something to shrug off. Don't be proud of ignorance. The problem is that the perspective expressed by the GP comment is a pure expression of the "don't know what you don't know" adage. Sure, you can hammer out solutions to problems, but the more exposure you've got to more concepts in your field, 1. the bigger your toolkit and 2. the quicker you can start drawing conclusions about the problem. I'm actually pretty shocked someone's confessing to not knowing what big O notation is and proud of it.
- hermannj314 14y ago
  > O(2^n) equal to O(3^n) Yep. So I looked into it and it seems they are not equal. Every f(n) in the set O(2^n) belongs to O(3^n). While this means that O(2^n) is a subset of O(3^n), we can see from the trival case f(n)=3^n that O(3^n) is not a subset O(2^n) since 3^n > 2^n for all n as n approaches infinity, or there is no k such that is exists an n0, such that all n > n0 implies 3^n < k*2^n, therefore the two sets are not equal. Great. I still don't see how I am more qualified to do absolutely anything in life.
  - radagaisus 14y ago
    That's a great textbook summary, now for applications: You got an array of your friends, an array of people who upvoted this post and an array of people who replied to this post. Filter all your friends who upvoted and replied to this post. Now, before you write the code, how fast/slow will it run? for 1,000 friends? 1,000,000? will the runtime grow extremely fast? why? Here's a Redis command that intersects two keys - http://redis.io/commands/sinter http://redis.io/commands/sinter - the complexity is "O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets." - do you understand why? do you understand when it will be fast and when will it be slow?
gargleblaster 14y ago
I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.
- crntaylor 14y ago
  It is perfectly well formulated. The notation O(f(n)) denotes a set of functions. The question is asking if the two sets O(2^n) and O(3^n) are the same set.
  - alexkus 14y ago
    I think the OP is looking for a bit more of an answer than a simple Yes/No.
    - anonymouz 14y ago
      He is also asking "Why?", i.e., for a proof[1] to back up your Yes/No answer. Seems like a perfectly good question. [1] Calculation, if you prefer.
  - nandemo 14y ago
    That's right. Some people get confused due to the rather unfortunate convention of writing f(n) = O(n) instead of the correct f(n) ∈ O(n).
- oggy 14y ago
  It's a perfectly sensible question. Knowing that both O(2^n) and O(3^n) are sets, and using the definition of set equality, it asks whether "f in O(2^n)" implies "f in O(3^n)", and vice versa. Only one of the implications holds...
  - deleted 14y ago
    [deleted]
dscrd 14y ago
Hmm, does all this imply that a blue-collar IT-workers' class is rising? When I was working during the summers at construction sites in my youth, I noted that everybody all the time complained about the impractical decisions the engineers and architects had made, and grumbling that they had to be there to fix them. Would they have been happier if they wouldn't have been needed at all? (disclaimer: I tend to change my shirt between white-collar and blue-collar [figuratively, of course] where I work)
- flatline 14y ago
  Interesting analogy. I think it more strongly implies that for the type of applications most frequently written, general intelligence and experience trump theoretical knowledge. Honestly the education you get from a BS in comp sci (the level of knowledge the post addresses) isn't going to qualify you for much more than the guy who has 4 years of experience on his résumé. Much less in some circumstances actually. This is a strange field.
- mattdeboard 14y ago
  (Shameless plug) I just wrote about this very thing on Friday: http://mattdeboard.net/2012/10/05/larry-the-software-guy/ http://mattdeboard.net/2012/10/05/larry-the-software-guy/ Not my best writing ever but that round's already downrange. Plus there's an excellent response from Alex Feinberg in the comments.
irahul 14y ago
> But I did have to answer this question: why does the application crash? "Oh...that's because the developer that was pontificating yesterday about how heap operations behave asymptotically forgot to check if the database connection was open before he called the Save method. Apparently, such arcane trivia is beneath him. I can fix it." False dichotomy. You posit the developer who understands asymptotic notation can't figure out why does the application crash, or how to write to databases. I don't see how understanding asymptotic notation negatively affects someone's programming ability..
- hermannj314 14y ago
  > I don't see how understanding asymptotic notation negatively affects someone's programming ability Why would it make them worse?* I was just arguing it doesn't necessarily make them better. Just because you are a bad developer doesn't mean you get better when you learn about asymptotic behavior or heapsort or O-notation. Lots of really bad developers know about those things. And lots of really bad developers don't know about them as well. Knowledge of those items is neither sufficient nor necessary to be either a competent or incompetent developer (at least for reasonable definitions of both competent and developer). * Ok - maybe too much knowledge has some odd 2nd order negative effects on productivity: analysis paralysis, over-confidence, unwillingness to ask for help, programming toward a theoretically pure solution rather than a pragmatic solution.

Altaco 14y ago

Meanwhile, you discover a long time down the road that the algorithm you thought was fine is actually incredibly slow when scaled to large inputs because you didn't have a good understanding of runtime analysis. Or maybe, as you say, understanding more things makes you worse at coding. Who knows.

waterlesscloud 14y ago
I guess I'm not buying that Big-O is a necessary requirement to understand how fast or slow an algorithm will be. It could be that someone understands and uses the process behind it without being at all familiar with the notation.

jrabone 14y ago

Some things you can look up quickly. Being functionally innumerate is not something you can fix with Google. The tedious details of whatever god-forsaken CRUD framework is flavour-of-the-week with the cool kids probably WERE beneath him.

deleted 14y ago
[deleted]

radagaisus 14y ago

from all the questions this is the one you MUST know if you want me (or anyone) to trust you with a piece of code. It takes one hour (in wikipedia!) to learn everything you'll need for a day-to-day work complexity assessment with the Big O notation. They asked us this questions on our high school final exams, I'm sure you'll manage.

mattdeboard 14y ago
Yeah, I mean, I'm also a self-taught, workaday programmer, and I agree with you. Understanding time complexity to a degree that you can communicate about it isn't something to shrug off. Don't be proud of ignorance. The problem is that the perspective expressed by the GP comment is a pure expression of the "don't know what you don't know" adage. Sure, you can hammer out solutions to problems, but the more exposure you've got to more concepts in your field, 1. the bigger your toolkit and 2. the quicker you can start drawing conclusions about the problem. I'm actually pretty shocked someone's confessing to not knowing what big O notation is and proud of it.
hermannj314 14y ago
> O(2^n) equal to O(3^n) Yep. So I looked into it and it seems they are not equal. Every f(n) in the set O(2^n) belongs to O(3^n). While this means that O(2^n) is a subset of O(3^n), we can see from the trival case f(n)=3^n that O(3^n) is not a subset O(2^n) since 3^n > 2^n for all n as n approaches infinity, or there is no k such that is exists an n0, such that all n > n0 implies 3^n < k*2^n, therefore the two sets are not equal. Great. I still don't see how I am more qualified to do absolutely anything in life.
- radagaisus 14y ago
  That's a great textbook summary, now for applications: You got an array of your friends, an array of people who upvoted this post and an array of people who replied to this post. Filter all your friends who upvoted and replied to this post. Now, before you write the code, how fast/slow will it run? for 1,000 friends? 1,000,000? will the runtime grow extremely fast? why? Here's a Redis command that intersects two keys - http://redis.io/commands/sinter http://redis.io/commands/sinter - the complexity is "O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets." - do you understand why? do you understand when it will be fast and when will it be slow?

gargleblaster 14y ago

I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.

crntaylor 14y ago
It is perfectly well formulated. The notation O(f(n)) denotes a set of functions. The question is asking if the two sets O(2^n) and O(3^n) are the same set.
- alexkus 14y ago
  I think the OP is looking for a bit more of an answer than a simple Yes/No.
  - anonymouz 14y ago
    He is also asking "Why?", i.e., for a proof[1] to back up your Yes/No answer. Seems like a perfectly good question. [1] Calculation, if you prefer.
- nandemo 14y ago
  That's right. Some people get confused due to the rather unfortunate convention of writing f(n) = O(n) instead of the correct f(n) ∈ O(n).
oggy 14y ago
It's a perfectly sensible question. Knowing that both O(2^n) and O(3^n) are sets, and using the definition of set equality, it asks whether "f in O(2^n)" implies "f in O(3^n)", and vice versa. Only one of the implications holds...
- deleted 14y ago
  [deleted]

dscrd 14y ago

Hmm, does all this imply that a blue-collar IT-workers' class is rising? When I was working during the summers at construction sites in my youth, I noted that everybody all the time complained about the impractical decisions the engineers and architects had made, and grumbling that they had to be there to fix them. Would they have been happier if they wouldn't have been needed at all? (disclaimer: I tend to change my shirt between white-collar and blue-collar [figuratively, of course] where I work)

flatline 14y ago
Interesting analogy. I think it more strongly implies that for the type of applications most frequently written, general intelligence and experience trump theoretical knowledge. Honestly the education you get from a BS in comp sci (the level of knowledge the post addresses) isn't going to qualify you for much more than the guy who has 4 years of experience on his résumé. Much less in some circumstances actually. This is a strange field.
mattdeboard 14y ago
(Shameless plug) I just wrote about this very thing on Friday: http://mattdeboard.net/2012/10/05/larry-the-software-guy/ http://mattdeboard.net/2012/10/05/larry-the-software-guy/ Not my best writing ever but that round's already downrange. Plus there's an excellent response from Alex Feinberg in the comments.

irahul 14y ago

> But I did have to answer this question: why does the application crash? "Oh...that's because the developer that was pontificating yesterday about how heap operations behave asymptotically forgot to check if the database connection was open before he called the Save method. Apparently, such arcane trivia is beneath him. I can fix it." False dichotomy. You posit the developer who understands asymptotic notation can't figure out why does the application crash, or how to write to databases. I don't see how understanding asymptotic notation negatively affects someone's programming ability..

hermannj314 14y ago
> I don't see how understanding asymptotic notation negatively affects someone's programming ability Why would it make them worse?* I was just arguing it doesn't necessarily make them better. Just because you are a bad developer doesn't mean you get better when you learn about asymptotic behavior or heapsort or O-notation. Lots of really bad developers know about those things. And lots of really bad developers don't know about them as well. Knowledge of those items is neither sufficient nor necessary to be either a competent or incompetent developer (at least for reasonable definitions of both competent and developer). * Ok - maybe too much knowledge has some odd 2nd order negative effects on productivity: analysis paralysis, over-confidence, unwillingness to ask for help, programming toward a theoretically pure solution rather than a pragmatic solution.