6 ms·

Big-O notation explained by a self-taught programmer

100 points by maxt 10y ago

adsofhoads 10y ago
Extensively incorrect.
c0achmcguirk 10y ago
My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants even know what Big-O notation is. It doesn't seem to impact hiring decisions though. We haven't turned anyone down because they miss that question. I think it's because anyone who has programmed for a year or so professionally already understands the concept of inefficient algorithms. They don't need to measure it mathematically, just learn how to optimize.
- allan_s 10y ago
  I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certainly the same guy that one day will bring in the team's "tips and tricks" channel an article or an insight that will make the team's knowledge grow too.
  - erikbye 10y ago
    How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array? We are no longer talking about a programmer then. Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work. Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.
    - digital_ins 10y ago
      I started off disagreeing with your statement but as I read further, I became a believer. In fact, "gotcha" and other trick questions are the worst, but understanding CS fundamentals shows that you were paying attention in class and are probably interested (if not passionate) about CS. If not, there are hundreds of other openings that the candidate can apply to.
    - binarycrusader 10y ago
      How can anyone applying for a programming job not know Big-O notation? That's CS101. You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming. Or they may have taken some CS classes, not enough to have covered that particular concept. I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts. Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.
      - ivanhoe 10y ago
        But still you had to hear about it sometimes, somewhere, it's mentioned in pretty much any serious text on algorithms. Thing is that many people see it mentioned, but never bother to stop & learn what it's all about... and that's telling something about their approach to programming (and life) in general.
        binarycrusader 10y ago
        Sorry, but, it doesn't tell you anything. The world of computers is full of things to learn about, more than almost any one person could learn in a lifetime. People usually learn about what interests them, or what they need to know. It's entirely possible to be an accomplished programmer and never really learn big-O notation just as some programmers never learn assembly or C. Think about it differently, big-O wasn't widely discussed or well known until the 1970s, thanks to Donald Knuth who popularized it. Then consider that many programmers who learned programming may have done so before it was widely known and some may have learned programming from those same people. Are those programmers from roughly 1980 and earlier any less a programmer because they weren't aware of or didn't use big-O notation? Of course not. Is big-O notation something most programmers should consider learning? Yes. But we should not seek to exclude others from a profession simply because they don't meet arbitrary criteria we think is necessary when they are clearly already actively engaged in that profession.
- user5994461 10y ago
  That makes sense. Big-O notation is so overrated. A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O. http://homepages.e3.net.nz/~djm/containerchoice.png http://homepages.e3.net.nz/~djm/containerchoice.png
  - bogomipz 10y ago
    > "That makes sense. Big-O notation is so overrated." Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated? Isn't that a bit like saying "Algebra is so overrated"? Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979. https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth-12 https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth... Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.
    - mikebenfield 10y ago
      I think (hope?) that user5994461's post was tongue in cheek. BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.
      - BeetleB 10y ago
        Mathematicians used it for asymptotic expansions of mathematical expressions. Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.
      - bogomipz 10y ago
        I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : ) Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature. This is the source I am referring to from 1976 SIGACT News: http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron... On page 21 or page 4 of the PDF: "I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. " On page 22 or page 5 of the PDF: "The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."
allan_s 10y ago
After seeing a lot of peers being mislead by big O I think most of big O articles on the web, for the sake of clarity or simplicity omits to express one thing if we admits functions * square_big_o O(n²) * linear_big_o O(n) then the statement time(squarre_big_o(x)) > time(linear_big_0(x)) is not necessary true for every value of x because the actual complexity could be * 1000+1000*N * 2+N² in which case most of the time you will chose the square one, because practically it will be faster. without this in mind, you got peer who tell you that this thing is faster because the algorithm is O(n) versus O(n²), though we're talking about a function that will always have n < 10, but yesterday night they read an article about big O and now they have to throw a "let's think about the big O" remarks for every single problem we meet
- Bahamut 10y ago
  Except if one knows what the definition of big O is, there is nothing to be misled by. What big O tells you is what is the function bounded by after a constant lower bound on the input. One always want to do performance testing to see whether it comes into play even when it comes to more practical applications such as in code.
mrcactu5 10y ago
Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?
- R_haterade 10y ago
  Sometimes. Sometimes you just need to throw things in the oven until the first one browns up. I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both algorithms, it's just that for the graph structure, the operation count for dijkstra was much lower. It was the first one to brown up.
  - bogomipz 10y ago
    Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.
    - R_haterade 10y ago
      I will have to check this out as I'm in a lot of places where speed matters these days. Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?
      - bogomipz 10y ago
        Its both. Here are some links: Video Lectures are here: https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms and the book: http://aofa.cs.princeton.edu/home/ http://aofa.cs.princeton.edu/home/ Also a youtube - short history of algorithm analysis by Sedgewick is worth a watch: https://www.youtube.com/watch?v=qap2MyBTSZk https://www.youtube.com/watch?v=qap2MyBTSZk
dizzystar 10y ago
As a self-taught, I always get nervous when I see articles explaining Big O because they are almost always wrong. While this one is mostly correct, it is a bit simplistic and misleading, and it could use considerable annotations. The "scary" Wikipedia article has examples that are more nuanced than what is written here; the first example shows a constant time algorithm with nested for loops. I take issue with the math fearing throughout the article. Time complexity is math, period. There is no getting around this fact, and the sooner you accept it, the sooner you learn that the math isn't that difficult, and the sooner you realize that, without some intuition on what the math is saying, you'll never really have a firm grasp of Big O or any of the other variations. And also, why no mention of log time?
- Waterluvian 10y ago
  As a self taught programmer who did no math in university, the most valuable thing to me was the discovery that the math really isn't scary. Once you understand the symbols and notation, most concepts are rather easy, given you commit time to learning it. I strayed away for so long until I watched the MIT lecture series on algorithms and it all just clicked. The best feeling was was seeing the math on the chalk board for how you determine the complexity of operations on various graph layouts and just getting it. I struggled in high school math and rarely got that feeling in class. It was just one of those, "holy crap... It's all just an array and how we organize the data in that array that gives various benefits and drawbacks!" Incredibly empowering. Edit: This is the series I watched: https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLU...
  - code777777 10y ago
    Would you please share the link to the MIT lecture series? It may help the rest of us too. Thanks!
    - Waterluvian 10y ago
      https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP... I used YouTube to slow down and speed up the videos as necessary. Watched some parts a few times. Had a notepad out.
achr2 10y ago
The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...
- BjoernKW 10y ago
  In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.
  - _greim_ 10y ago
    Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.
    - FreeFull 10y ago
      It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm
      - stouset 10y ago
        This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.
        10y ago
castratikron 10y ago
Didn't know that the "O" in Big-O actually means "order". I guess it doesn't really matter too much. If you really wanted to get theoretical, you could also talk about the whole family, including little-O, big-omega, little-omega, etc. :)
- p333347 10y ago
  The usage "big omega" and "little omega" always makes me chuckle, as they translate to "big big oh" and "little big oh".
- bogomipz 10y ago
  I don't believe this is correct, I believe O if for Greek letter Omnicron, just as the other Greek letters are used Big Theta and Big Omega are used in discussing bounds in time complexity. I think O meaning order would be a retronym.

100 points by maxt 10y ago

Extensively incorrect.

My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants even know what Big-O notation is. It doesn't seem to impact hiring decisions though. We haven't turned anyone down because they miss that question. I think it's because anyone who has programmed for a year or so professionally already understands the concept of inefficient algorithms. They don't need to measure it mathematically, just learn how to optimize.

allan_s 10y ago
I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certainly the same guy that one day will bring in the team's "tips and tricks" channel an article or an insight that will make the team's knowledge grow too.
- erikbye 10y ago
  How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array? We are no longer talking about a programmer then. Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work. Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.
  - digital_ins 10y ago
    I started off disagreeing with your statement but as I read further, I became a believer. In fact, "gotcha" and other trick questions are the worst, but understanding CS fundamentals shows that you were paying attention in class and are probably interested (if not passionate) about CS. If not, there are hundreds of other openings that the candidate can apply to.
  - binarycrusader 10y ago
    How can anyone applying for a programming job not know Big-O notation? That's CS101. You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming. Or they may have taken some CS classes, not enough to have covered that particular concept. I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts. Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.
    - ivanhoe 10y ago
      But still you had to hear about it sometimes, somewhere, it's mentioned in pretty much any serious text on algorithms. Thing is that many people see it mentioned, but never bother to stop & learn what it's all about... and that's telling something about their approach to programming (and life) in general.
      - binarycrusader 10y ago
        Sorry, but, it doesn't tell you anything. The world of computers is full of things to learn about, more than almost any one person could learn in a lifetime. People usually learn about what interests them, or what they need to know. It's entirely possible to be an accomplished programmer and never really learn big-O notation just as some programmers never learn assembly or C. Think about it differently, big-O wasn't widely discussed or well known until the 1970s, thanks to Donald Knuth who popularized it. Then consider that many programmers who learned programming may have done so before it was widely known and some may have learned programming from those same people. Are those programmers from roughly 1980 and earlier any less a programmer because they weren't aware of or didn't use big-O notation? Of course not. Is big-O notation something most programmers should consider learning? Yes. But we should not seek to exclude others from a profession simply because they don't meet arbitrary criteria we think is necessary when they are clearly already actively engaged in that profession.
user5994461 10y ago
That makes sense. Big-O notation is so overrated. A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O. http://homepages.e3.net.nz/~djm/containerchoice.png http://homepages.e3.net.nz/~djm/containerchoice.png
- bogomipz 10y ago
  > "That makes sense. Big-O notation is so overrated." Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated? Isn't that a bit like saying "Algebra is so overrated"? Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979. https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth-12 https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth... Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.
  - mikebenfield 10y ago
    I think (hope?) that user5994461's post was tongue in cheek. BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.
    - BeetleB 10y ago
      Mathematicians used it for asymptotic expansions of mathematical expressions. Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.
    - bogomipz 10y ago
      I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : ) Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature. This is the source I am referring to from 1976 SIGACT News: http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron... On page 21 or page 4 of the PDF: "I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. " On page 22 or page 5 of the PDF: "The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."

allan_s 10y ago

After seeing a lot of peers being mislead by big O I think most of big O articles on the web, for the sake of clarity or simplicity omits to express one thing if we admits functions * square_big_o O(n²) * linear_big_o O(n) then the statement time(squarre_big_o(x)) > time(linear_big_0(x)) is not necessary true for every value of x because the actual complexity could be * 1000+1000*N * 2+N² in which case most of the time you will chose the square one, because practically it will be faster. without this in mind, you got peer who tell you that this thing is faster because the algorithm is O(n) versus O(n²), though we're talking about a function that will always have n < 10, but yesterday night they read an article about big O and now they have to throw a "let's think about the big O" remarks for every single problem we meet

Bahamut 10y ago
Except if one knows what the definition of big O is, there is nothing to be misled by. What big O tells you is what is the function bounded by after a constant lower bound on the input. One always want to do performance testing to see whether it comes into play even when it comes to more practical applications such as in code.

mrcactu5 10y ago

Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?

R_haterade 10y ago
Sometimes. Sometimes you just need to throw things in the oven until the first one browns up. I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both algorithms, it's just that for the graph structure, the operation count for dijkstra was much lower. It was the first one to brown up.
- bogomipz 10y ago
  Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.
  - R_haterade 10y ago
    I will have to check this out as I'm in a lot of places where speed matters these days. Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?
    - bogomipz 10y ago
      Its both. Here are some links: Video Lectures are here: https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms and the book: http://aofa.cs.princeton.edu/home/ http://aofa.cs.princeton.edu/home/ Also a youtube - short history of algorithm analysis by Sedgewick is worth a watch: https://www.youtube.com/watch?v=qap2MyBTSZk https://www.youtube.com/watch?v=qap2MyBTSZk

dizzystar 10y ago

As a self-taught, I always get nervous when I see articles explaining Big O because they are almost always wrong. While this one is mostly correct, it is a bit simplistic and misleading, and it could use considerable annotations. The "scary" Wikipedia article has examples that are more nuanced than what is written here; the first example shows a constant time algorithm with nested for loops. I take issue with the math fearing throughout the article. Time complexity is math, period. There is no getting around this fact, and the sooner you accept it, the sooner you learn that the math isn't that difficult, and the sooner you realize that, without some intuition on what the math is saying, you'll never really have a firm grasp of Big O or any of the other variations. And also, why no mention of log time?

Waterluvian 10y ago
As a self taught programmer who did no math in university, the most valuable thing to me was the discovery that the math really isn't scary. Once you understand the symbols and notation, most concepts are rather easy, given you commit time to learning it. I strayed away for so long until I watched the MIT lecture series on algorithms and it all just clicked. The best feeling was was seeing the math on the chalk board for how you determine the complexity of operations on various graph layouts and just getting it. I struggled in high school math and rarely got that feeling in class. It was just one of those, "holy crap... It's all just an array and how we organize the data in that array that gives various benefits and drawbacks!" Incredibly empowering. Edit: This is the series I watched: https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb https://www.youtube.com/watch?v=HtSuA80QTyo&index=1&list=PLU...
- code777777 10y ago
  Would you please share the link to the MIT lecture series? It may help the rest of us too. Thanks!
  - Waterluvian 10y ago
    https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP... I used YouTube to slow down and speed up the videos as necessary. Watched some parts a few times. Had a notepad out.

achr2 10y ago

The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...

BjoernKW 10y ago
In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.
- _greim_ 10y ago
  Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.
  - FreeFull 10y ago
    It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm
    - stouset 10y ago
      This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.
      - 10y ago

castratikron 10y ago

Didn't know that the "O" in Big-O actually means "order". I guess it doesn't really matter too much. If you really wanted to get theoretical, you could also talk about the whole family, including little-O, big-omega, little-omega, etc. :)

p333347 10y ago
The usage "big omega" and "little omega" always makes me chuckle, as they translate to "big big oh" and "little big oh".
bogomipz 10y ago
I don't believe this is correct, I believe O if for Greek letter Omnicron, just as the other Greek letters are used Big Theta and Big Omega are used in discussing bounds in time complexity. I think O meaning order would be a retronym.