10 ms·

WTF Is Big O Notation?

143 points by soheilpro 8y ago

yxmayt 8y ago
A precise way of being imprecise.
derekp7 8y ago
My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then processing, the records that the module cares about, it does the selection (which typically returns 1 - 10 records), sorts them, processes the record from the top of the list, then throws the rest of the initial select results away. It then goes back to the DB an does the same select, and repeats the process. End result: if the queue gets backed up to 100, or 1000 records, the process never catches up. You have to temporarily change the status of the inbound records to something else, then put maybe 10 at a time back to pending. There are countless other times I've seen similar types of issues where on small data sets the code runs fine, but the performance degrades to n^2, or even worse is when it degrades in a factorial manor. And the worst of it is that if I talk to the developers using common CS notation (such as, your algorithm should have logarithmic or at worse linear degradation as the input queue grows, and it is behaving exponentially), their eyes glaze over.
- eindiran 8y ago
  That's not my experience as a software engineer at all. In fact, I would say that I see people worrying about writing algorithms that are asymptotically optimal (well before that should ever be a consideration) 10x as often as I see people failing to consider the efficiency of the algorithms they write.
  - derekp7 8y ago
    Do you think this is due to a difference between working at a place that has software requiring a specific non-computer related skill set (such as medical diagnostics software), vs being at a place that hires primarily CS grads for regular software? Other developers that I've worked around at previous jobs were in manufacturing (Informix 4GL devs), and an IT services company, among others. The one common thread I've seen though is they tend to be impressed by what I can do in C, for example, or helping them get to the root of an issue they have (I will typically reverse engineer what they are doing from the outside looking in, using things like strace, then writing up an analysis of what I see from the systems side). Another recent example is a case where the app needed to start a number of sub-processes. So the dev used an equiv of a system() call, which spawned a bash shell, to do a ps -ef |grep process_name |grep -v grep |grep -v vi |grep -v vim |grep -v less, to see if the process was running, then doing another system() call to start the sub process. The whole string would be repeated for each sub process, and then they wondered why it took 8 minutes to start all their sub interfaces when they deployed to a larger customer that needed 700 interfaces started (instead of the typical 20 - 50). Oh, and after they would start an interface, the code would do the "ps..." commands on all the other interfaces to update an internal table on their status.
    - eindiran 8y ago
      That might very well be there difference. My coworkers are almost exclusively people who studied CS, and several wrote C professionally at some point.
    - mixmastamyk 8y ago
      I don't think one needs to be a CS grad to recognize such a poor design.
- User23 8y ago
  One of the things I like about the C++ STL is once you learn the idioms, the API tells you whether an operation is "fast." I don't really care if a line programmer can give me the formal definition of O(x), but I sure want him to know if an operation is appropriate to call in a loop. That's speaking as a professional. As someone who finds CS fascinating, I'm appalled by the lack of interest many professional developers have in what is one of the most rigorous and elegant fields of mathematical inquiry. Even so I don't expect others to care about the things I do.
  - sidlls 8y ago
    Why are you appalled? As a physicist I'm not appalled by the lack of interest most engineers have in fundamental theory that I know inside out. The reason is precisely because I understand there's a difference between practical applications and theoretical inquiry.
- Retric 8y ago
  The example you gave is not really a Big O issue. It's the extra DB calls adding a huge constant that's the problem not the underlying algorithm. O(x) can be horrible when the constant is 1/10th of a second each record. This may be a case of the developers not understanding your ORM tooling. They get something that works, and don't quite what's going on under the hood.
- chrisseaton 8y ago
  > I find it fairly rare for developers that I work with that think of Big O considerations when writing their code Do you not hear people talk about 'accidentally quadratic' quite a bit? I hear practising developers talk about that a lot. They seem to have a good idea of what to avoid.
  - pvg 8y ago
    'Accidentally quadratic' happens and is talked about precisely because much of the time, there's not much reason to think about Big O in many practical software development situations.
- imtringued 8y ago
  It doesn't sound like teaching Big O Notation would help your coworkers write faster software. You would be better off by teaching them how to use databases properly.
  - deleted 8y ago
    [deleted]
- roel_v 8y ago
  " is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code." Do you mean that as in 'people I work with don't care about this, therefore it's not necessary' or as in 'people I work with are clowns who don't even know foundations'? Because (I think) I'm seeing replies to your post interpreting it both ways.
  - derekp7 8y ago
    I wouldn't use the word clowns, because they are really good at other areas. In this case, the developers focus on a development environment that isn't widely used in the US, and I believe that they haven't had a formal CS education (more of the same type of self taught that I am).
    - roel_v 8y ago
      "I wouldn't use the word clowns" Nah it was just an expression from my part, didn't mean to say that anyone not thinking about algorithmic complexity when writing any piece of software is a hack :)
- p1necone 8y ago
  I don't think knowing about big O notation (or really much cs theory) is a requirement for reasoning about this particular case. "network/sql calls are slow" and "don't do the same work multiple times when it isn't necessary" would be enough.
- codingdave 8y ago
  > their eyes glaze over. Sounds like a communication problem to me. Non-academic developers might not know "Big O notation". But they absolutely know that nested loops are way less efficient than single loops. They know that some code performs better than other code. And while they might be writing inefficient code, that is an opportunity to talk to them and help them improve. If you come at them with academic terms (right though you may be), and their eyes glaze over, try talking about the actual change you are seeking. Especially in the database world, as less experienced developers might not know that database performance can be tuned by how you use it. We all were new once. So educate them. Kindly.
- deathanatos 8y ago
  > I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. Every time I choose between a set and a vector in code, I'm essentially drawing on my knowledge of their big-O properties to choose the right one for whatever task I have at hand. I wouldn't say that's the only piece of CS theory I use, either. I routinely run across problems that are best modeled as DAGs (any dependency relationship between items boils down to this quickly). I use DB theory any time I design a database table. I draw on language theory to write parsers. Most of it is reflexive, I think, at this point, but it doesn't change that a "vector" is the right structure b/c I don't need O(1) lookup, or I'd like indexing.
User23 8y ago
The formal definition is a fairly gentle introduction to logical math. Here is a decent enough write-up: https://justin.abrah.ms/computer-science/understanding-big-o-formal-definition.html https://justin.abrah.ms/computer-science/understanding-big-o...
davismwfl 8y ago
That was a good write up, and it will help people. I come from the self taught side, and find that it is critical to know these things when you work in certain areas of a code base and once you reach a certain level. But I don't expect everyone needs to have the same level of understanding. I also find interviewers asking detailed questions about Big O and specific different algorithms just idiotic, especially the esoteric ones I've been asked in the past and/or heard asked. When I interview someone, all I want to know is that you know there is a difference and know to look when it matters. My method for learning if a candidate understands this all is to get people to choose data structures based upon different problem sets I will give them and then ask the pros and cons. The more questions they ask about usage usually the more they understand in my experience. And this is just way more informative as a hiring manager as you will learn more if they understand what they are saying, versus if they can regurgitate something they memorized from a book or website.
- labster 8y ago
  Having for the most part avoided the computer science department during my earth science education, this is helpful. I have sort of an intrinsic idea of what's going on -- self-joins can easily compare a data set with every other member of the data set, and hit O(N²). And that if your N is 5, the DB will probably going spend more time parsing SQL than executing your query, so no point in optimizing. So I don't understand or care about what the definition is, but it's useful tool to think about how slow your code can be.
roel_v 8y ago
(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins. Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the article, this is most obvious in the following sentence: "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)." No you don't. If your table is sorted, you'll need only 1 operation to find 'Academy Dinosaur', because it's your first element. What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same. But my point is that to understand big O notation for real world impact, you first need to understand the concepts the article mentions, and then you also need to be able to accurately assess the lower-dimensional terms that are left out, and estimate them. (preempting counter sniping: this is assuming that titles are unique) (to put this in other words, an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' where x is a constant; but we leave that out because at the margin, it doesn't matter (i.e. is dwarfed by the O(n) term. But when n is small and x is large, x becomes dominant, so assessing the effects of the complexity, in the real world, need to keep the expected magnitude of n in mind.)
- worik 8y ago
  ...an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' No it should not. (O(N) + x) is O(N). That is how it works, is spoken about... What it means! It is a very simple minded article, and IMO misleading, but it is better than "(O(N) + x) is bigger than O(N)". In the sense of order analysis, it is not.
  - roel_v 8y ago
    Well yes, that's what I said, although I guess I could have used 'n + x operations' to keep it consistent with the article and still in line with the formal definition.
bogomipz 8y ago
>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i < 1000; i++) for (int j = n; j >= 1; j = j / 2) // do something EDIT: initialized j to the val of n on the inner loop per the comments below.
- anon946 8y ago
  Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?
  - bogomipz 8y ago
    The inner loop is log(N), it halves the value of J after every iteration. The "do something" was meant to stand for a constant time operation so that it's N log N. But my point was really that if you told an interviewer that it was O(N^2) simply because it contained nested for loops it would be a very clear sign that you didn't fully grasp Big O.
    - anon946 8y ago
      Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).
    - vecter 8y ago
      It's a subtle point, but anon946 was pointing out that since your loops are fixed at 1000, this entire thing is O(1) (granted, with a large constant). You should change all of the "1000" to "n". That would make it O(n lg n). edit: you've now edited the inner loop to be n, but the outer loop is still 1000. This is still wrong, as the entire algorithm is now just O(lg n).
    - enedil 8y ago
      Nah, every algorithm that is O(N logN) is also O(n^2). That would be a sign, that you as an interviewer didn't fully grasp Big O.
toadi 8y ago
I mostly don't think about it too much. If I have a piece of code that seems slow I make it less complicated and mostly look up the big-O. Reason is that I only had a few time in my 20 year career that I really had issues with this.
- mixmastamyk 8y ago
  True, after a few years of experience you recognize pitfalls to avoid. I remember figuring this out on my own as a kid writing a chat client, years before learning O terminology. As the number of clients reached ten performance dropped and quickly realized I needed to handle the situation more efficiently and did. Doesn't provide the smug satisfaction of using the academic notation/jargon given in tech interviews and hn threads however.
gpm 8y ago
This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways). Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.
- briankelly 8y ago
  There's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
  - gpm 8y ago
    Oh cool, hadn't seen that!
- deathanatos 8y ago
  There was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics. My googling dug up [1], but I'm not sure if that's it or not. My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about. > 16/32 bit pointers for small arrays? It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out. [1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html ¹I'm a software engineer, not a physicist.
ratling 8y ago
This is legitimately a good post.
mbell 8y ago
> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think? The thing is, I don't care about 'time complexity', I care about performance. Big O can serve as a useful datapoint for what the performance may be, but it's only that, one data point. e.g. It's not uncommon to find that a 'worse' algorithm/data structure in Big O terms will out perform a 'better' one because the 'worse' one has better cache locality. So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.
- robconery 8y ago
  OP here - Big O notation is simply shorthand math. When you're discussing things in this way, time complexity and performance are the same thing. When you care about resource usage (memory etc) that's space complexity, which is different. Either way, they're good things to understand. >So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster. Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.
  - mbell 8y ago
    > time complexity and performance are the same thing By definition, they are not. > Mathematically the log n is always faster :) No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.
    - robconery 8y ago
      I believe we're talking past each other. Big O has nothing to do with "actual run time*. It doesn't care what about the number of inputs you have - just that you have them. Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster. Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.
ykevinator 8y ago
It's a great post and everyone stop flexing. Learn basic complexity if you don't know it, it has huge dividends.
gaze 8y ago
Oh ffs another article about Big-O without the actual definition anywhere in it. Put it at the end after motivating it, put it at the beginning and then explain it, I don’t care. Just actually give it at some point.
js2 8y ago
Formal definition from my ancient copy of Sedgewick: A function g(N) is said to be O(f(N)) if there exist constants c₀ and n₀ such that g(N) is less than c₀f(N) for all N > N₀. Continuing: "Informally, this encapsulates the notion of “is proportional to” and frees the analyst from considering the details of particular machine characteristics. Furthermore, the statement that the running time of an algorithm is O(f(N)) is independent of the algorithm's input. Since we're interested in studying the algorithm, not the input or the implementation, the O-notation is a useful way to state upper bounds on running time which are independent of both inputs and implementation details." I'll also repeat this bit from the end of the analysis chapter: Perspective: Many of the algorithms in this book have been subjected to detailed mathematical analysis and performance studies far too complex to be discussed here. Indeed, it is on the basis of such studies that we are able to recommend many of the algorithms we discuss. Not all algorithms are worthy of such intense scrutiny; indeed during the design process, it is preferable to work with approximate performance indicators to guide the design process without extraneous detail. As the design becomes more refined, so must the analysis, and more sophisticated mathematical tools need to be applied. Often, the design process leads to detailed complexity studies that lead to "theoretical" algorithms rather far from any particular application. It is a common mistake to assume that rough analyses from complexity studies will translate immediately to efficient practical algorithms: this often leads to unpleasant surprises. On the other hand, computational complexity is a powerful tool for suggesting departures in design upon which important new methods can be based. One should not use an algorithm without some indication of how it will perform. [...]
auraham 8y ago
I really like the post, I think it is very intuitive. However, it was a bit confusing at the end. Consider these scenarios: (1) looking for an item in you cart using a hash, and (2) looking for an item in the whole databse using a hash. From the article, I assume that (1) is O(1) because of the hash, but for (2) it is O(log n). Maybe I am confusing a hash and an index. If so, what is the difference?

143 points by soheilpro 8y ago

A precise way of being imprecise.

My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then processing, the records that the module cares about, it does the selection (which typically returns 1 - 10 records), sorts them, processes the record from the top of the list, then throws the rest of the initial select results away. It then goes back to the DB an does the same select, and repeats the process. End result: if the queue gets backed up to 100, or 1000 records, the process never catches up. You have to temporarily change the status of the inbound records to something else, then put maybe 10 at a time back to pending. There are countless other times I've seen similar types of issues where on small data sets the code runs fine, but the performance degrades to n^2, or even worse is when it degrades in a factorial manor. And the worst of it is that if I talk to the developers using common CS notation (such as, your algorithm should have logarithmic or at worse linear degradation as the input queue grows, and it is behaving exponentially), their eyes glaze over.

eindiran 8y ago
That's not my experience as a software engineer at all. In fact, I would say that I see people worrying about writing algorithms that are asymptotically optimal (well before that should ever be a consideration) 10x as often as I see people failing to consider the efficiency of the algorithms they write.
- derekp7 8y ago
  Do you think this is due to a difference between working at a place that has software requiring a specific non-computer related skill set (such as medical diagnostics software), vs being at a place that hires primarily CS grads for regular software? Other developers that I've worked around at previous jobs were in manufacturing (Informix 4GL devs), and an IT services company, among others. The one common thread I've seen though is they tend to be impressed by what I can do in C, for example, or helping them get to the root of an issue they have (I will typically reverse engineer what they are doing from the outside looking in, using things like strace, then writing up an analysis of what I see from the systems side). Another recent example is a case where the app needed to start a number of sub-processes. So the dev used an equiv of a system() call, which spawned a bash shell, to do a ps -ef |grep process_name |grep -v grep |grep -v vi |grep -v vim |grep -v less, to see if the process was running, then doing another system() call to start the sub process. The whole string would be repeated for each sub process, and then they wondered why it took 8 minutes to start all their sub interfaces when they deployed to a larger customer that needed 700 interfaces started (instead of the typical 20 - 50). Oh, and after they would start an interface, the code would do the "ps..." commands on all the other interfaces to update an internal table on their status.
  - eindiran 8y ago
    That might very well be there difference. My coworkers are almost exclusively people who studied CS, and several wrote C professionally at some point.
  - mixmastamyk 8y ago
    I don't think one needs to be a CS grad to recognize such a poor design.
User23 8y ago
One of the things I like about the C++ STL is once you learn the idioms, the API tells you whether an operation is "fast." I don't really care if a line programmer can give me the formal definition of O(x), but I sure want him to know if an operation is appropriate to call in a loop. That's speaking as a professional. As someone who finds CS fascinating, I'm appalled by the lack of interest many professional developers have in what is one of the most rigorous and elegant fields of mathematical inquiry. Even so I don't expect others to care about the things I do.
- sidlls 8y ago
  Why are you appalled? As a physicist I'm not appalled by the lack of interest most engineers have in fundamental theory that I know inside out. The reason is precisely because I understand there's a difference between practical applications and theoretical inquiry.
Retric 8y ago
The example you gave is not really a Big O issue. It's the extra DB calls adding a huge constant that's the problem not the underlying algorithm. O(x) can be horrible when the constant is 1/10th of a second each record. This may be a case of the developers not understanding your ORM tooling. They get something that works, and don't quite what's going on under the hood.
chrisseaton 8y ago
> I find it fairly rare for developers that I work with that think of Big O considerations when writing their code Do you not hear people talk about 'accidentally quadratic' quite a bit? I hear practising developers talk about that a lot. They seem to have a good idea of what to avoid.
- pvg 8y ago
  'Accidentally quadratic' happens and is talked about precisely because much of the time, there's not much reason to think about Big O in many practical software development situations.
imtringued 8y ago
It doesn't sound like teaching Big O Notation would help your coworkers write faster software. You would be better off by teaching them how to use databases properly.
- deleted 8y ago
  [deleted]
roel_v 8y ago
" is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code." Do you mean that as in 'people I work with don't care about this, therefore it's not necessary' or as in 'people I work with are clowns who don't even know foundations'? Because (I think) I'm seeing replies to your post interpreting it both ways.
- derekp7 8y ago
  I wouldn't use the word clowns, because they are really good at other areas. In this case, the developers focus on a development environment that isn't widely used in the US, and I believe that they haven't had a formal CS education (more of the same type of self taught that I am).
  - roel_v 8y ago
    "I wouldn't use the word clowns" Nah it was just an expression from my part, didn't mean to say that anyone not thinking about algorithmic complexity when writing any piece of software is a hack :)
p1necone 8y ago
I don't think knowing about big O notation (or really much cs theory) is a requirement for reasoning about this particular case. "network/sql calls are slow" and "don't do the same work multiple times when it isn't necessary" would be enough.
codingdave 8y ago
> their eyes glaze over. Sounds like a communication problem to me. Non-academic developers might not know "Big O notation". But they absolutely know that nested loops are way less efficient than single loops. They know that some code performs better than other code. And while they might be writing inefficient code, that is an opportunity to talk to them and help them improve. If you come at them with academic terms (right though you may be), and their eyes glaze over, try talking about the actual change you are seeking. Especially in the database world, as less experienced developers might not know that database performance can be tuned by how you use it. We all were new once. So educate them. Kindly.
deathanatos 8y ago
> I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. Every time I choose between a set and a vector in code, I'm essentially drawing on my knowledge of their big-O properties to choose the right one for whatever task I have at hand. I wouldn't say that's the only piece of CS theory I use, either. I routinely run across problems that are best modeled as DAGs (any dependency relationship between items boils down to this quickly). I use DB theory any time I design a database table. I draw on language theory to write parsers. Most of it is reflexive, I think, at this point, but it doesn't change that a "vector" is the right structure b/c I don't need O(1) lookup, or I'd like indexing.

User23 8y ago

The formal definition is a fairly gentle introduction to logical math. Here is a decent enough write-up: https://justin.abrah.ms/computer-science/understanding-big-o-formal-definition.html https://justin.abrah.ms/computer-science/understanding-big-o...

davismwfl 8y ago

That was a good write up, and it will help people. I come from the self taught side, and find that it is critical to know these things when you work in certain areas of a code base and once you reach a certain level. But I don't expect everyone needs to have the same level of understanding. I also find interviewers asking detailed questions about Big O and specific different algorithms just idiotic, especially the esoteric ones I've been asked in the past and/or heard asked. When I interview someone, all I want to know is that you know there is a difference and know to look when it matters. My method for learning if a candidate understands this all is to get people to choose data structures based upon different problem sets I will give them and then ask the pros and cons. The more questions they ask about usage usually the more they understand in my experience. And this is just way more informative as a hiring manager as you will learn more if they understand what they are saying, versus if they can regurgitate something they memorized from a book or website.

labster 8y ago
Having for the most part avoided the computer science department during my earth science education, this is helpful. I have sort of an intrinsic idea of what's going on -- self-joins can easily compare a data set with every other member of the data set, and hit O(N²). And that if your N is 5, the DB will probably going spend more time parsing SQL than executing your query, so no point in optimizing. So I don't understand or care about what the definition is, but it's useful tool to think about how slow your code can be.

roel_v 8y ago

(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins. Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the article, this is most obvious in the following sentence: "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)." No you don't. If your table is sorted, you'll need only 1 operation to find 'Academy Dinosaur', because it's your first element. What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same. But my point is that to understand big O notation for real world impact, you first need to understand the concepts the article mentions, and then you also need to be able to accurately assess the lower-dimensional terms that are left out, and estimate them. (preempting counter sniping: this is assuming that titles are unique) (to put this in other words, an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' where x is a constant; but we leave that out because at the margin, it doesn't matter (i.e. is dwarfed by the O(n) term. But when n is small and x is large, x becomes dominant, so assessing the effects of the complexity, in the real world, need to keep the expected magnitude of n in mind.)

worik 8y ago
...an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' No it should not. (O(N) + x) is O(N). That is how it works, is spoken about... What it means! It is a very simple minded article, and IMO misleading, but it is better than "(O(N) + x) is bigger than O(N)". In the sense of order analysis, it is not.
- roel_v 8y ago
  Well yes, that's what I said, although I guess I could have used 'n + x operations' to keep it consistent with the article and still in line with the formal definition.

bogomipz 8y ago

>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i < 1000; i++) for (int j = n; j >= 1; j = j / 2) // do something EDIT: initialized j to the val of n on the inner loop per the comments below.

anon946 8y ago
Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?
- bogomipz 8y ago
  The inner loop is log(N), it halves the value of J after every iteration. The "do something" was meant to stand for a constant time operation so that it's N log N. But my point was really that if you told an interviewer that it was O(N^2) simply because it contained nested for loops it would be a very clear sign that you didn't fully grasp Big O.
  - anon946 8y ago
    Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).
  - vecter 8y ago
    It's a subtle point, but anon946 was pointing out that since your loops are fixed at 1000, this entire thing is O(1) (granted, with a large constant). You should change all of the "1000" to "n". That would make it O(n lg n). edit: you've now edited the inner loop to be n, but the outer loop is still 1000. This is still wrong, as the entire algorithm is now just O(lg n).
  - enedil 8y ago
    Nah, every algorithm that is O(N logN) is also O(n^2). That would be a sign, that you as an interviewer didn't fully grasp Big O.

toadi 8y ago

I mostly don't think about it too much. If I have a piece of code that seems slow I make it less complicated and mostly look up the big-O. Reason is that I only had a few time in my 20 year career that I really had issues with this.

mixmastamyk 8y ago
True, after a few years of experience you recognize pitfalls to avoid. I remember figuring this out on my own as a kid writing a chat client, years before learning O terminology. As the number of clients reached ten performance dropped and quickly realized I needed to handle the situation more efficiently and did. Doesn't provide the smug satisfaction of using the academic notation/jargon given in tech interviews and hn threads however.

gpm 8y ago

This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways). Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.

briankelly 8y ago
There's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- gpm 8y ago
  Oh cool, hadn't seen that!
deathanatos 8y ago
There was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics. My googling dug up [1], but I'm not sure if that's it or not. My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about. > 16/32 bit pointers for small arrays? It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out. [1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html ¹I'm a software engineer, not a physicist.

ratling 8y ago

This is legitimately a good post.

mbell 8y ago

> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think? The thing is, I don't care about 'time complexity', I care about performance. Big O can serve as a useful datapoint for what the performance may be, but it's only that, one data point. e.g. It's not uncommon to find that a 'worse' algorithm/data structure in Big O terms will out perform a 'better' one because the 'worse' one has better cache locality. So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.

robconery 8y ago
OP here - Big O notation is simply shorthand math. When you're discussing things in this way, time complexity and performance are the same thing. When you care about resource usage (memory etc) that's space complexity, which is different. Either way, they're good things to understand. >So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster. Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.
- mbell 8y ago
  > time complexity and performance are the same thing By definition, they are not. > Mathematically the log n is always faster :) No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.
  - robconery 8y ago
    I believe we're talking past each other. Big O has nothing to do with "actual run time*. It doesn't care what about the number of inputs you have - just that you have them. Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster. Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.

ykevinator 8y ago

It's a great post and everyone stop flexing. Learn basic complexity if you don't know it, it has huge dividends.

gaze 8y ago

Oh ffs another article about Big-O without the actual definition anywhere in it. Put it at the end after motivating it, put it at the beginning and then explain it, I don’t care. Just actually give it at some point.

js2 8y ago

Formal definition from my ancient copy of Sedgewick: A function g(N) is said to be O(f(N)) if there exist constants c₀ and n₀ such that g(N) is less than c₀f(N) for all N > N₀. Continuing: "Informally, this encapsulates the notion of “is proportional to” and frees the analyst from considering the details of particular machine characteristics. Furthermore, the statement that the running time of an algorithm is O(f(N)) is independent of the algorithm's input. Since we're interested in studying the algorithm, not the input or the implementation, the O-notation is a useful way to state upper bounds on running time which are independent of both inputs and implementation details." I'll also repeat this bit from the end of the analysis chapter: Perspective: Many of the algorithms in this book have been subjected to detailed mathematical analysis and performance studies far too complex to be discussed here. Indeed, it is on the basis of such studies that we are able to recommend many of the algorithms we discuss. Not all algorithms are worthy of such intense scrutiny; indeed during the design process, it is preferable to work with approximate performance indicators to guide the design process without extraneous detail. As the design becomes more refined, so must the analysis, and more sophisticated mathematical tools need to be applied. Often, the design process leads to detailed complexity studies that lead to "theoretical" algorithms rather far from any particular application. It is a common mistake to assume that rough analyses from complexity studies will translate immediately to efficient practical algorithms: this often leads to unpleasant surprises. On the other hand, computational complexity is a powerful tool for suggesting departures in design upon which important new methods can be based. One should not use an algorithm without some indication of how it will perform. [...]

auraham 8y ago

I really like the post, I think it is very intuitive. However, it was a bit confusing at the end. Consider these scenarios: (1) looking for an item in you cart using a hash, and (2) looking for an item in the whole databse using a hash. From the article, I assume that (1) is O(1) because of the hash, but for (2) it is O(log n). Maybe I am confusing a hash and an index. If so, what is the difference?