3 ms·

I generally agree, most logic questions are useless, but Big-O notation I use every day. Programmers who don't understand the performance difference between Arr

I generally agree, most logic questions are useless, but Big-O notation I use every day. Programmers who don't understand the performance difference between Array#include? and Set#include? in ruby are dangerous!

randomdata 14y ago
I'm curious to know where you use the notation in daily programming. In code comments? Discussions with other developers? Other documentation? I use the spirt of Big-O almost daily, but do the actual calculations rarely, and basically never use the notation. With some experience, you quickly get an intuitive feel for execution time, which is good enough in most cases.
- kamaal 14y ago
  Actually using something like a math notation to solve a programming problem is asking for too much. What are those general problems which can't be solved by standard libraries, frameworks and IDE's these days? And even if you are facing problems that mandate you to roll out your stuff how much of that requires these math tricks. Given all this, if you truly want to hire a math geek to get some magic done. I guess you are looking at a very small pool of people to hire from and it should hardly be a problem to hire one.
  - to3m 14y ago
    Big-O notation is hardly "math geek" stuff. I'd not call this comment ridiculous, because I might have misunderstood it, but catch me in my cups and ask me for my true opinion and maybe I'd say that. Big-O notation is pretty basic, and very useful. Combined with a memorized table of powers of two (you don't need all of them - I know up to 2^20, and this has proven sufficient - just enough so you can guess log N for a given value) you have a good chance at being able to make quick calculations about time and space requirements for things. Which, since we don't have infinitely fast computers with infinite amounts of memory, often comes in handy.
    - kamaal 14y ago
      I'm not talking about Big-O. I'm talking about the general theme of these interviews. Besides that I still don't understand this. I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm. Its always how the programmer can take pressure, how he can contribute to making the project happen, getting things done, how he can collaborate with fellow team mates, how he responds under times of crisis, how good he is with tools, what are his everyday practices, does he write unit tests, does he do code reviews, does he document the API's he writes, how does he package his code, how update he is with software world(tools, framework and techniques) etc etc. Lets be frank, Its always these things that are relevant today in practical everyday software projects today. Unfortunately people hardly ask questions on these and then complain of bad software practices among people these days.
      - pnathan 14y ago
        > I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm. Either your team does horrifically easy work, or no one has told you about their abstract work. I am sorry, but even writing CRUD apps I have to think about the informatics of the system to make it work reasonably well.
- andrewvc 14y ago
  If I'm reading up on a new technology it's useful to understand what they mean when they say 'operations are O(1)'. Additionally, when writing an API for use by other developers its useful to say, this operation runs in constant time, that one in logarithmic time. Redis, for example, mentions the computational complexity of all operations in its docs. Additionally, everyone should know that most decent sorting algorithms are O(n log n), and understand the implications of that.
- Zarel 14y ago
  The last time I talked about Big-O notation was three days ago, when talking about whether or not inserting/deleting from a list should be done online or queued up: Zarel: and for insertions, aren't they O(nm) for n insertions into a list of size m either way? Cathy: inserting n elements into a list of size m when done with queueing requires at most m iterations Cathy: when not done using a queue, it requires at most n*m iterations Cathy: a factor of n is the difference Cathy: of course, n might be pretty small, depending on how many insertions happen in the debounce wnidow Cathy: n might be 10-15 Zarel: how do you insert n elements into a list of size m in m iterations? Cathy: iterate over the list of m elements Cathy: well, i guess you'd need to sort the list of n elements first Zarel: oh, I see, I forgot about sorting the list Zarel: so it'd be O(n+m) Zarel: which is admittedly much faster for our purposes Zarel: well, considering n is likely to be approximately 5, "much" might be an exaggeration Cathy: in any case, i agree that inserting/deletion approach is the right way to do this Zarel: incidentally if we wanted we could apply certain optimizations to improve an insertion from O(n) Zarel: for instance, binary search Cathy: it's not immediately obvious whether that is faster than the sorted queued Zarel: actually, that's not a bad idea regardless Cathy: but it's certainly faster than the naive single insertion Zarel: I mean, O(n log m) is significantly faster than O(n+m) Zarel: when n is ~5 and m is ~1500 Cathy: true, and it actually makes it clear that using a queue is unnecessary I don't know of a better way to discuss optimizing an inner loop than to use big O notation.
ianstallings 14y ago
All one really needs to know about Big-O is that nested data lists can be exponentially harder to process. If you understand that then you understand the need for it and when the time arises for you to create these type of structures you'll calculate the time needed to process them accordingly using said method. In turn helping you predict future performance and avoiding bottlenecks.
matwood 14y ago
In your example, I see Big-O as a side effect of using the right data structure for the job. If you need a data structure to hold items that should not be duplicated or ordered then a set (or hash which is likely what the ruby set is based on) is what you want to use because it is not only faster but conveys meaning to the maintenance programmer. If you need order maintained then move up to an ordered set. If you need to keep distinct duplicates then some sort of list is going to be needed (Array, Linked, etc...). I guess what I'm trying to say is that Big-O between a Set and Array do not matter if you can't use a set to begin with. If the problem fits a set then using a set is right regardless of the performance implications. I do agree with your overall premise of laziness though. Most programmers default to a list likely because it is the first thing ever taught, and for some reason rarely think beyond it. For me, part of the fun of solving coding problems is finding the best fit data structure :)

randomdata 14y ago

I'm curious to know where you use the notation in daily programming. In code comments? Discussions with other developers? Other documentation? I use the spirt of Big-O almost daily, but do the actual calculations rarely, and basically never use the notation. With some experience, you quickly get an intuitive feel for execution time, which is good enough in most cases.

kamaal 14y ago
Actually using something like a math notation to solve a programming problem is asking for too much. What are those general problems which can't be solved by standard libraries, frameworks and IDE's these days? And even if you are facing problems that mandate you to roll out your stuff how much of that requires these math tricks. Given all this, if you truly want to hire a math geek to get some magic done. I guess you are looking at a very small pool of people to hire from and it should hardly be a problem to hire one.
- to3m 14y ago
  Big-O notation is hardly "math geek" stuff. I'd not call this comment ridiculous, because I might have misunderstood it, but catch me in my cups and ask me for my true opinion and maybe I'd say that. Big-O notation is pretty basic, and very useful. Combined with a memorized table of powers of two (you don't need all of them - I know up to 2^20, and this has proven sufficient - just enough so you can guess log N for a given value) you have a good chance at being able to make quick calculations about time and space requirements for things. Which, since we don't have infinitely fast computers with infinite amounts of memory, often comes in handy.
  - kamaal 14y ago
    I'm not talking about Big-O. I'm talking about the general theme of these interviews. Besides that I still don't understand this. I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm. Its always how the programmer can take pressure, how he can contribute to making the project happen, getting things done, how he can collaborate with fellow team mates, how he responds under times of crisis, how good he is with tools, what are his everyday practices, does he write unit tests, does he do code reviews, does he document the API's he writes, how does he package his code, how update he is with software world(tools, framework and techniques) etc etc. Lets be frank, Its always these things that are relevant today in practical everyday software projects today. Unfortunately people hardly ask questions on these and then complain of bad software practices among people these days.
    - pnathan 14y ago
      > I don't even know the last time anybody around me ever had a problem or a show stopper problem anything to do with Big-O or an algorithm. Either your team does horrifically easy work, or no one has told you about their abstract work. I am sorry, but even writing CRUD apps I have to think about the informatics of the system to make it work reasonably well.
andrewvc 14y ago
If I'm reading up on a new technology it's useful to understand what they mean when they say 'operations are O(1)'. Additionally, when writing an API for use by other developers its useful to say, this operation runs in constant time, that one in logarithmic time. Redis, for example, mentions the computational complexity of all operations in its docs. Additionally, everyone should know that most decent sorting algorithms are O(n log n), and understand the implications of that.
Zarel 14y ago
The last time I talked about Big-O notation was three days ago, when talking about whether or not inserting/deleting from a list should be done online or queued up: Zarel: and for insertions, aren't they O(nm) for n insertions into a list of size m either way? Cathy: inserting n elements into a list of size m when done with queueing requires at most m iterations Cathy: when not done using a queue, it requires at most n*m iterations Cathy: a factor of n is the difference Cathy: of course, n might be pretty small, depending on how many insertions happen in the debounce wnidow Cathy: n might be 10-15 Zarel: how do you insert n elements into a list of size m in m iterations? Cathy: iterate over the list of m elements Cathy: well, i guess you'd need to sort the list of n elements first Zarel: oh, I see, I forgot about sorting the list Zarel: so it'd be O(n+m) Zarel: which is admittedly much faster for our purposes Zarel: well, considering n is likely to be approximately 5, "much" might be an exaggeration Cathy: in any case, i agree that inserting/deletion approach is the right way to do this Zarel: incidentally if we wanted we could apply certain optimizations to improve an insertion from O(n) Zarel: for instance, binary search Cathy: it's not immediately obvious whether that is faster than the sorted queued Zarel: actually, that's not a bad idea regardless Cathy: but it's certainly faster than the naive single insertion Zarel: I mean, O(n log m) is significantly faster than O(n+m) Zarel: when n is ~5 and m is ~1500 Cathy: true, and it actually makes it clear that using a queue is unnecessary I don't know of a better way to discuss optimizing an inner loop than to use big O notation.

ianstallings 14y ago

All one really needs to know about Big-O is that nested data lists can be exponentially harder to process. If you understand that then you understand the need for it and when the time arises for you to create these type of structures you'll calculate the time needed to process them accordingly using said method. In turn helping you predict future performance and avoiding bottlenecks.

matwood 14y ago

In your example, I see Big-O as a side effect of using the right data structure for the job. If you need a data structure to hold items that should not be duplicated or ordered then a set (or hash which is likely what the ruby set is based on) is what you want to use because it is not only faster but conveys meaning to the maintenance programmer. If you need order maintained then move up to an ordered set. If you need to keep distinct duplicates then some sort of list is going to be needed (Array, Linked, etc...). I guess what I'm trying to say is that Big-O between a Set and Array do not matter if you can't use a set to begin with. If the problem fits a set then using a set is right regardless of the performance implications. I do agree with your overall premise of laziness though. Most programmers default to a list likely because it is the first thing ever taught, and for some reason rarely think beyond it. For me, part of the fun of solving coding problems is finding the best fit data structure :)