15 ms·

Big O Notation – Explained as easily as possible

489 points by optimalsolver 6y ago

hprotagonist 6y ago
https://nedbatchelder.com/text/bigo/bigo.html https://nedbatchelder.com/text/bigo/bigo.html is also a good intro read.
xiphias2 6y ago
Just read a book on algorithms. They are timeless, unlike APIs, so it's worth the effort to study them.
adamnemecek 6y ago
Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n). That’s literally all there is to it.
- jkaptur 6y ago
  What if there are recursive function calls?
  - pmiller2 6y ago
    Then you get to have fun solving a recurrence relation. :-)
    - johndough 6y ago
      If you don't like "fun", WolframAlpha can solve those for you. :-) https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%282%29+%3D+1%2C+f%28n%29+%3D+f%28n+-+1%29+%2B+f%28n+-+2%29 https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%28...
      - pmiller2 6y ago
        Sure, but if you're not on the spot in an interview, the master theorem is simple enough to apply: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Generic_form https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_al...
      - commandnotfound 6y ago
        Thank you, but for the link provided it only says that these are the Fibonacci numbers and nothing more. Yes, you can click on this F(n) (how can you even know this is a link), but anyways.
  - miguelrochefort 6y ago
    branchesᵈᵉᵖᵗʰ
- nkozyra 6y ago
  That covers most of the algorithms you'll see in a coding interview test, but there's a ton more complexities outside of search spaces, sorts and nested O(n) loops. Even some graph operations will leave familiar territory.
- creata 6y ago
  That's not even close to all there is to it. Complexity analysis is a relatively young field with lots of deceptively simple unsolved problems. For a simple example of how it's a lot more than that, follow Tarjan's proof of the disjoint set's amortized time complexity[0]. It's not at all obvious, even though the disjoint set is a very simple and practical data structure. [0]: http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20Good%20But%20Not%20Linear%20Set%20Union%20Algorithm.%20Tarjan.pdf http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20G...
  - andi999 6y ago
    So what would be a deceptivly simple unsolved problem?
    - creata 6y ago
      Wikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements. https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science#Computational_complexity https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...
      - adamnemecek 6y ago
        P == NP on analog quantum computers. A light prism performs a diagonalization which can be used to do factorization in O(1).
        rytill 6y ago
        Factorization of arbitrarily large numbers? I doubt it.
        adamnemecek 6y ago
        Yes.
- dragontamer 6y ago
  Strassen algorithm is 7-multiplications for a 2x2 matrix. https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm A matrix can always be split into groups of sub-matrix, and the groups of sub-matrix is itself a matrix. Applying Strassen algorithm recursively is therefore O(n^log2(7)) == O(n^2.8ish).
  - adamnemecek 6y ago
    The article covers none of those.
bjeds 6y ago
If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one out of many members in a family of notations that has a very specific mathematical definition, other common ones being small-o and big-theta. Analysis of algorithms is more difficult than it appears. If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).
- bitexploder 6y ago
  It is still a useful conceptual framework. Maybe this sparks someone’s interest. Agree it is much harder than it appears :)
- nicoburns 6y ago
  The problem with that is that informal use of big-o like notation is a lot more intuitive than the fancy language in your explanantion. Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.
  - deleted 6y ago
    [deleted]
  - sabas123 6y ago
    Why wouldn't you be able to just say "worst case n^2?"
    - smichel17 6y ago
      Dropping a constant
pmiller2 6y ago
Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significant amount of mathematical background. But, that definition isn't that hard. It's simply: f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). And, if you're in an analysis of algorithms context, it's even easier, because you typically don't have to worry about this absolute value business. Well, that M is essentially the reason you get to drop constant multiples of f(x). And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0. (No need to prove this, because this is what makes the "less significant" terms less significant.) I would also like to add that the equals sign in f(x) = O(g(x)) is one of the most useful abuses of notation that I know of, but it can be misleading. It doesn't behave at all like a real equality because it's not symmetric, but it is transitive and reflexive. It actually acts more like set membership than equality.
- casion 6y ago
  You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.
  - roywiggins 6y ago
    The short version is that the fastest-growing term dominates all the others and for large xs the smaller terms round down to zero. Since big-O notation is about how the complexity grows for large inputs, you can assume the input is arbitrarily large, and you'll notice that the complexity is completely determined by the fastest-growing term. You drop the constant because it doesn't alter how the complexity grows as the input increases.
  - pmiller2 6y ago
    Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite to assume for anyone who wants to be throwing around terms like "Big-O." If it's not too intrusive, may I ask what your graduate degrees are?
xyzelement 6y ago
It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.
- windowojji 6y ago
  > it's applied to a small enough input The whole point of big-O notation is to analyze algorithms as they're applied to input of size `n` larger than some `n_0`. Of course it's not useful for small inputs - it's explicitly about large inputs. > it's implemented very efficiently On large inputs, it's very hard see how, say, a linear algorithm with a quadratic algorithm regardless of how "efficiently" it's implemented. Assuming you're talking about something like cache friendliness or good register allocation?
  - xyzelement 6y ago
    Yeah we are talking about the same thing. I agree that what you are saying is deeply connected to value of Big O. I am just pointing out that people sometimes forget to consider these things.
- musingsole 6y ago
  Most people jump to an extreme hyperbole instead of the reality what they're grappling with. Big-O is just that algorithmatised. Many software systems must be designed to anticipate orders of magnitude growth in scale. However, I'm not sure about how most software systems grow -- not sure anyone really knows. We all have narratives about it, but it's a small, small subset of projects I know about that have an order of magnitude different number of users than when I first learned about them (other than moving to effectively 0).
- NationalPark 6y ago
  Yes, it's good to remember that complexity analysis is only a theoretical topic that motivates certain approaches. When performance matters, you measure your program/system and use that as the ultimate guide for your work. Cache locality and branch prediction are two examples of practical issues that the theoretical approach will often ignore.
dragontamer 6y ago
Big O is literally easier than the analytical alternative. I didn't "understand" Big-O until I read Donald Knuth's "Art of Computer Programming". I forget exactly where Knuth does this... but Knuth derives the _exact_ number of average runtime on some algorithm. (Where "average" is defined as all possible permutations of the input). I forget why or where this derivation was, but it was along the lines of 3nlog(n) + 5n +25, or something along those lines (I made up the numbers). Solving for the specific and exact runtime of a function is very, very, very difficult. Instead of doing that, Comp. Sci has decided that the easier Big-O is "good enough" for most purposes. That's it. Big-O is ALWAYS easier to calculate than the exact runtime. Yeah, its still hard in some cases, and there are situations like Radix sort (O(n)) vs Quicksort (O(n*log(n)), or Karatsuba multiplication vs optimal multiplication (like O(n^1.5) vs O(n^1.4...)) where the "slower Big-O" is better in practice. But such situations are rare, and are easily figured out through profiling. --------- So lets do some real-talk. Most programmers don't wait on their code anymore. Computers are so fast, that all this algorithmic complexity is a red herring compared to other issues. By and large, inefficient programming languages are being used in grossly inefficient ways and no one cares. For most practical purposes, profiling with a stopwatch is your go-to methodology for analyzing algorithms. If that's not good enough, then profiling with a dedicated profiler (which can statistically count specific situations: like cache-hits or branch-mispredictions, as well as how many times any particular line of code ran). That's the information you want and need. Take the runtimes, plot it on a log-log plot, fit a growth-exponent on the curve and BAM, you got O(n^whatever). Where Big-O comes in are the situations where you're waiting for your code to finish. You run your code, and you wait 10-minutes, 1-hour, 10-hours, 2-days... will your code finish? Do you have an infinite loop? Or is it actually making forward progress? If so, how long do you estimate it to last? (And indeed: Hollywood movies are known to take multiple days to render a single frame, so these situations come up every now an then in practice). Under such a situation, you can't really run a profiler or use a stopwatch. You probably can run a big-O analysis by pen-and-paper over your code however, and then get an estimate on the size of your data. You'll want to make sure that you're O(n) or O(n*log(n)). If you're getting O(n^2) or O(n^3) from an algorithm that's taking days to run... you might be in trouble.
lrossi 6y ago
If you really want to make it easy to understand, make it graphical. That is: benchmark the code, varying the input size, and plot the results. Almost anyone should be able to understand. This might also reveal effects that are not taken into account by Big O notation, as not all algorithms that have the same complexity have the same performance. But I see it as a plus.
- mhh__ 6y ago
  The coefficients are what can bite you. Also amortized analysis, e.g. appending to a std::vector is O(n) in the worst case but O(1) almost all the time (the O(n) spikes come at something like every n = golden_ratio^k * initial size for integer k)
- kevin_thibedeau 6y ago
  It isn't uncommon for algorithms with "worse" algorithmic complexity to perform better than the faster alternative because the constant overhead of setting up the "better" algorithm eats all the performance gains. Sequential search is faster than binary search for short lists. You need to test to see where the crossover happens on your platform.
  - kaba0 6y ago
    Not necessarily set-up time, but either constants can reverse the roles, or the fact that CPUs are hardly complex and the model most often used in analyzing algorithms is more simple and doesn’t map too well to things like caches, branch-prediction and the like.
axaxs 6y ago
I think a minimal reproduction of each common complexity would be a way more helpful addition. Someone with little math background is going to have no idea what log even means, much less what causes it.
alok-g 6y ago
>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?
- mhh__ 6y ago
  You'd need to know the exact details of the implementation of your arithmetic library, but it would depend on the integer in question which makes analysis a little harder so adding two numbers would become some function O(f(n, m)) where n, m are the two numbers or some property of them (length, digits etc.)
- qsort 6y ago
  It generally changes the analysis very little but makes it more annoying, which is why arithmetic is usually taken to be O(1). Formally speaking you'd have to specify a computational model to be able to talk about complexity (there is no such thing as 'complexity' but only 'complexity respective to a model'; e.g. you can change the big-O complexity on Turing machines by using more tapes). The computational model of a book like CLRS is "arithmetic is O(1), but we're not going to abuse that bug".
- aweinstock 6y ago
  The contrast between Gauss-Jordan[0] and the Bareiss algorithm[1] is a good example of explicitly handling the length of the numbers in bits as part of the runtime. Gauss-Jordan is O(n^3) if you consider addition and multiplication to be constant-time, but if it operates on arbitrary-precision integers, it can get exponentially slow[2]. The Bareiss algorithm avoids this worst-case behavior by choosing the pivots in a slightly more involved manner, which avoids building up large intermediate values. [0]: https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency https://en.wikipedia.org/wiki/Gaussian_elimination#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: https://staff.itee.uq.edu.au/havas/fh97.pdf https://staff.itee.uq.edu.au/havas/fh97.pdf, Section 3.1's "Construction A" is a specific matrix that exhibits the worst-case behavior.
infogulch 6y ago
I noticed some comments here discussing the right prerequisite knowledge to understand big-O and friends. I propose limits. I think it would be a lot easier for someone to understand how to think about big-O if they already understood limits. Lim [x -> inf] O(f(x))/O(g(x)) If you know limits, you know you how and why you can ignore all but the highest power term, how to compare and simplify other kinds of terms, etc. Though maybe that's too much to ask of someone new.
- windowojji 6y ago
  > Lim [x -> inf] O(f(x))/O(g(x)) I understand both limits and I've taught asymptotic analysis in the past. O(f(x)) and O(g(x)) are sets. How does one divide two sets? This explanation is ill formed.
- psibi 6y ago
  I don't think limits is a good way to understand it because of the reasons here: https://math.stackexchange.com/a/3222489/124772 https://math.stackexchange.com/a/3222489/124772
tracyhenry 6y ago
Remotely related: the Theory of Computation course I took (by Michael Sipser) gave me a more fundamental understanding of algorithmic complexity than I had through solving algorithmic puzzles in high-level languages: https://math.mit.edu/~sipser/18404/ https://math.mit.edu/~sipser/18404/
a_a_a_a 6y ago
lkjhlkjhlk
maweki 6y ago
What I always find a bit missing in such articles is what the n is. The author writes "If you consider "addition" to be 1 operation" and this seems kinda intuitive and is correct if we talk about normal machine integers. But adding two arbitrary integers might be somewhat linear in bit-width. And there we have it: with a fixed bit-width, this becomes a constant term. So you might not want to talk about number of input terms as n, but also width of your terms (and python integers are arbitrary precision btw.). So yeah, this is an upper bound on how many "steps" you do for every input, but often enough it's not really clear what a step is, especially if you have several "steps" that relate do different forms of data retrieval and organization (which often are culprits for bad performance if you're done optimizing the number of loops). Sometimes you can hide behind some guaruantees that your hashset has constant lookup. But did you factor in whether the hash function is actually constant (or even fast, for that matter)?
- bnegreve 6y ago
  > often enough it's not really clear what a step is The steps are basic CPU operations such as load/store and basic arithmetic operations performed on fixed width type. I.e. things a CPU can do. > And there we have it: with a fixed bit-width, this becomes a constant term. It makes sense because that is how the CPU works: arithmetic operations on fixed width types are performed in constant time in the CPU ALU. Adding anything below 2^32 requires the same number of cylces. It is only confusing when you confuse basic CPU operations with basic python instructions (an arbitrary precision addition is certainly not a simple operation from the cpu perspective)
  - maweki 6y ago
    > The steps are basic CPU operations such as load/store Only if you consider the result of a comparison as a "store" into the register. But again, comparing two objects might not be constant. The compiler I develop for my PhD, for example, uses (written in Haskell) somewhat nested sets and quite a few operations are dominated by the equality check. > It is only confusing when you confuse basic CPU operations with basic python instructions But the author did exactly that, when they considered addition to be constant, which is a good approximation for small integers, but wrong in python. And really, you do have to consider those intricacies, that's why I chose this example, as sets and maps in python are basically hashmaps, you can assume constant lookup, for example, if your hash function works in constant time. And again, this begs the question what the n is. Usually we would set n as the number of items in a collection for its retrieval operation. But you actually also have to consider the item being retrieved.
tromp 6y ago
Note that f(n) = O(g(n)) denotes an asymptotic upper bound. So it would be correct (if confusing) to say that 2n+3 = O(n^2). This is important for use in algorithmic complexity because we may not always be able to determine the running time even up to a constant, but can more easily infer an upper bound. Using Omega instead denotes an asymptotic lower bound. To denote both, you use Theta: f(n) = Theta(g(n)) means that for two constants 0 < c1 < c2 and large enough n, we have c1 < f(n)/g(n) < c2. Finally, little o denotes vanishing behaviour. f(n) = o(g(n)) when f(n)/g(n) goes to 0 in the limit.
- kaba0 6y ago
  A nitpick because this is an accepted notation, but as others mentioned in the thread: when someone writes 2n+3 = O(n) they mean 2n+3 \in O(n) (\in is little epsilon in latex, that is “element of set”), since O(f) is the set of all functions that has “f as an upper bound”.
lordnacho 6y ago
The thing that didn't click for me was precisely the "try to count the operations" thing that the author mentions. In fact it's the wrong road to go down, it isn't the point of big-o, and yet that's how you're invited to think about it when the issue is presented in college. It's only natural to think "oh let's look at all the operations and add them up". I think of it pretty simply, but not in that formal big-theta/big-omega kind of way, because you want to just quickly have an idea of whether you'll write a really slow piece of code in general, not some best or worst case. The question is simply what growth model dominates the increase of time/space for the algo for each of the inputs? Imagine the algo is already processing millions of input A, and you now increase A by a factor of 10, 100, etc. This melts away all the setup costs, nothing machine specific like cache size matters, anything that isn't the dominating factor is swamped, and all you're left thinking about is probably how some loop expands. You also don't need to think about what coefficient that dominating term has, which you would if you tried to write an equation that took all the operations into account.
- kaba0 6y ago
  It was the contrary for me. I think it helps understanding that we are actually put a value to each line of code that gets executed, but instead of microbenchmarking, we do it in an abstract way, say print gets c1 constant, addition gets c2 and the like. For loops will multiply the instructions’ sum inside them by the number of times they get executed. And basically that’s it. You sum the whole thing and get something like (c1+c2)n+c3 for a for loop over an n element list or something with two instructions inside and one other outside the loop. Since these were arbitrary constants, c1 and c2 can be replaced by another one, so you’ve got cn+c3, and since (I’m not gonna be mathematically rigorous here) as n changes, it will be much larger than the others, we are only interested in it, hence it was an O(n) algorithm. The eye-opening thing about it was that for simple algorithms, I only need high-school math to analyze them for different measurements. Like, memory allocation is costly for this sort of application and I want to measure that, just count each malloc instead! (But do note that it is quite hard/impossible to rigorously analyze programs for modern CPUs with cache misses and the like)
breck 6y ago
One thought I’ve never had: “I wish I hadn’t been so much time thinking about Big O notation, power laws, and orders of magnitudes”
kadoban 6y ago
That in _no_ way explained big-O notation. It explained the basics of counting things to do with algorithms. Which is kind of fine, really. But why bother saying it's going to explain big-O?
joe_91 6y ago
Much better explained than in my computer science lectures! Nice simple examples. It's such an important topic to grasp too if you're going to end up working with software!
hisfastness 6y ago
Not a bad intro and appreciate the intention on keeping it short and simple, but personally for me I think Grokking Algorithms has the best beginner explanations of Big O and basic algorithms / data structures. If I had to share resources with a learner, I'd suggest Grokking as an item to go deeper on after reading this article.
deleted 6y ago
[deleted]
lamename 6y ago
Also a nice quick ref here https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/
ineedasername 6y ago
I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the moment "algorithms" we discussed in any learning material. Maybe it's just that it goes back to the common topic here on HN that there's a lot more inefficient code nowadays because faster processors & more memory helps to paper over the cracks. But if something like Big O isn't taught as one of the most primitive bits of knowledge in programming then I can't completely that trend either.
- matttb 6y ago
  Many, many developers did not go to school and have no 'CS' type learning
- racl101 6y ago
  I think this might be for the self taught crowd of developers who never formally took Comp Sci, yet, who are also wielding important positions in software development that pay as well if not more than the guys who did take comp sci. You'd be astounded how big this self taught cohort could be and how much power they wield. They do their job pretty well, and yet, the basics of computer science is something that they never learned. I met a senior guy the other day who had never heard of a freaking truth table for fuck's sake.
  - jobbo 6y ago
    I was dropped into the tech lead position at my job last year; I started in game design at art college, so having to run and gun has been fascinating. I'd be lying if I said I wasn't scared reading about much of the stuff in this comment section that really should be bread and butter. I'm talking to my boss to see if there's some kind of training program I can pick-up on the side to help me gather what should be the basics that I've missed out on, although we're so overloaded finding the time and money is challenging. I'm lucky it's mostly CRUD, but I can't help by worry every architecture decision I'm making is going to cost us massively down the road.
analog31 6y ago
I learned a couple of things during a brief teaching stint. First, no matter how much math your students learned in their high school and college courses, you should expect to re-teach the concepts that are needed for your lesson. It needn't be extensive, but your students will thank you for it. Second, don't introduce more than one hard concept at once. Asymptotes can be reviewed with pure math functions such as polynomials, but that's as far as they got in high school math. Then there are the other "interesting" orders such as log(n) that can be introduced, and you can show graphically why they're useful. Now you're ready to discuss the order of algorithms. I'm not a computer scientist, but that's how I learned it, and while I don't remember all of the algorithms today, I still understand the derivations of their orders when I see them.
kodah 6y ago
I learned to code as a kid and only met mathematicians who consider themselves programmers as an adult. Some opinion, maybe unpopular: Big O notation can be quite informally understood by normal people. It is academic people that make it and keep it challenging because it is how they understand the world. This is why interviews have stayed materially gruesome despite loud voices wishing it weren't so. It's the language of the people that rule this industry and you either learn it or leave. That said, we can change it too, if we want.
- asperous 6y ago
  I have met a lot of programmers that don't know about the concept nor do they proactively think to apply it. I do understand the disconnect between knowing snobby language and doing good work. Certainly you can be an amazing programmer and apply these ideas possibly without ever even being trained on them or knowing the jargon. In industry at least, a lot of work is communication so you have to know what things are commonly called to explain your thoughts to other people. and along those lines Mathematicians are the ones that are studying this concept in the abstract, so its useful to use their lingo because then you know where to find all the abstract knowledge on the subject. Finally I'll say of all the obscure terminology for things intuitively applied, Big O has to be one of the most common, followed by gang of 4s design patterns.
  - kodah 6y ago
    > In industry at least, a lot of work is communication so you have to know what things are commonly called to explain your thoughts to other people. and along those lines Mathematicians are the ones that are studying this concept in the abstract, so its useful to use their lingo because then you know where to find all the abstract knowledge on the subject. I think this is what I'm getting at. Mathematicians can adjust their language to communicate with a wider audience, especially on things as so commonly understood as Big O. It's a two way street, because you need to know and understand mathematical principles to be a good programmer, but if this is your only mode of understanding you are equally useless. There needs to be hiring gates for both.
- rramadass 6y ago
ncmncm 6y ago
Big-O notation was the only thing taught to me in a college (tech) class that I use. Everything else I use, I had already learned; you can pick up everything CS departments teach, just by reading. Engineering wasn't like that. It was taught so well, by Paul Cull, that it seemed obvious and hardly in need of a name. But I wish I had a nickel for every time some hotshot thinks that, because they got the right big-O performance, they are done. Where performance matters, big-O is is table stakes. There is typically an order of magnitude or two to be gained from that point.
mypalmike 6y ago
As someone who learns best from experience, my intuition for algorithmic complexity didn't really come from reading about it or solving problems in CS classes (though that was useful). It came from running tests on my own inefficient code and waiting for it to finish, wondering why my stupid computer was frozen. And then digging in and realizing my O(n^3) or whatever algorithm was not going to be sufficiently fast for production cases.
codesparkle 6y ago
A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.
- volkk 6y ago
  Should also add that an inefficient solution for a mostly fixed input size is still going to be efficient. If you have to write a double for loop but the outer loop is iterating on a 1000 element array and the inner one is operating on a 26 element array (e.g alphabet), it's still a fast and probably good enough solution.
  - gvx 6y ago
    Operating on a fixed size datatype is trivially O(1), too (because O(c) = O(1) when c is a constant).
- rramadass 6y ago
  Good caveat; beginners should not bother about any of this stuff. Focus on good modularity, clear code structure and language idioms and in general for readability.
- chii 6y ago
  And great programmers would knowingly solve a problem inefficiently, because it's easier to write and ship it to the customer, and thus prove that the problem being solved is valuable.
  - blackbear_ 6y ago
    Until, two years layer, the program needs one minute to start, every operation needs ten seconds to be executed and nobody knows why the program needs gigs of ram to stay idle and what to do about it.
- 6y ago
deleted 6y ago
[deleted]
PhantomBKB 6y ago
I liked it, but perhaps giving an example each of the different complexities that it talks about with the suitable use case would have been great. On that note, I'll take up the task of doing that in the near future.
dfdz 6y ago
Disclaimer: I am very familiar with big O notation and find it intuitive. However, I think the notation \lesssim or << which is common in upper level math courses, but not often discussed in undergraduate texts is much easier to explain, and should be introduced in lower level courses. You write f(n) \lesssim g(n) if there is an absolute constant C such that f(n) \le C g(n) the meaning is completely clear and by rearranging an expression it can replace big O notation. For example instead of writing f(n) = g(n) + O(h(n)) you write |f(n) - g(n)| \lesssim h(n) https://math.stackexchange.com/questions/1793395/who-introduced-the-notation-lesssim https://math.stackexchange.com/questions/1793395/who-introdu...
- gvx 6y ago
  If I understand correctly, f(n) << g(n) is equivalent to f(n) = o(g(n)), not f(n) = O(g(n)).
  - dfdz 6y ago
    It depends on the author/field. In analysis sometimes f(n) <<g(n) means f(n) = o(g(n)), but other times (especially in discrete math) f(n) << g(n) means f(n) = O(g(n)). Due to this ambiguity, I think the notation f(n) ~< g(n) or in latex f(n) \lesssim g(n) is more clear
WinterHoursTF 6y ago
I think calling it big O was a mistake. Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means.
- ColFrancis 6y ago
  Calling it big O is indeed a mistake (especially when you start using it with handwriting, o & O because difficult to distinguish). > Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means Tricky thing is, that's not what big O says. It's a statement about the asymptotic growth of a function which you can apply to a worst case. You'd be better off using "the worst case grows as at most". The distinction is important as you are ignoring two crucial things: the non-asymptotic behaviour and the coefficient of the asymptotic behaviour.
  - WinterHoursTF 6y ago
    I know I was just talking about what people always seem to mean by big O. Also it is what O is applied on most of the time.
alisaus 6y ago
I was a really bad girl. Punish me with your dick in my mouth. - https://adultlove.life https://adultlove.life
dikaio 6y ago
Beautiful.

489 points by optimalsolver 6y ago

hprotagonist 6y ago

https://nedbatchelder.com/text/bigo/bigo.html https://nedbatchelder.com/text/bigo/bigo.html is also a good intro read.

xiphias2 6y ago

Just read a book on algorithms. They are timeless, unlike APIs, so it's worth the effort to study them.

adamnemecek 6y ago

Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n). That’s literally all there is to it.

jkaptur 6y ago
What if there are recursive function calls?
- pmiller2 6y ago
  Then you get to have fun solving a recurrence relation. :-)
  - johndough 6y ago
    If you don't like "fun", WolframAlpha can solve those for you. :-) https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%282%29+%3D+1%2C+f%28n%29+%3D+f%28n+-+1%29+%2B+f%28n+-+2%29 https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%28...
    - pmiller2 6y ago
      Sure, but if you're not on the spot in an interview, the master theorem is simple enough to apply: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Generic_form https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_al...
    - commandnotfound 6y ago
      Thank you, but for the link provided it only says that these are the Fibonacci numbers and nothing more. Yes, you can click on this F(n) (how can you even know this is a link), but anyways.
- miguelrochefort 6y ago
  branchesᵈᵉᵖᵗʰ
nkozyra 6y ago
That covers most of the algorithms you'll see in a coding interview test, but there's a ton more complexities outside of search spaces, sorts and nested O(n) loops. Even some graph operations will leave familiar territory.
creata 6y ago
That's not even close to all there is to it. Complexity analysis is a relatively young field with lots of deceptively simple unsolved problems. For a simple example of how it's a lot more than that, follow Tarjan's proof of the disjoint set's amortized time complexity[0]. It's not at all obvious, even though the disjoint set is a very simple and practical data structure. [0]: http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20Good%20But%20Not%20Linear%20Set%20Union%20Algorithm.%20Tarjan.pdf http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20G...
- andi999 6y ago
  So what would be a deceptivly simple unsolved problem?
  - creata 6y ago
    Wikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements. https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science#Computational_complexity https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...
    - adamnemecek 6y ago
      P == NP on analog quantum computers. A light prism performs a diagonalization which can be used to do factorization in O(1).
      - rytill 6y ago
        Factorization of arbitrarily large numbers? I doubt it.
        adamnemecek 6y ago
        Yes.
dragontamer 6y ago
Strassen algorithm is 7-multiplications for a 2x2 matrix. https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm A matrix can always be split into groups of sub-matrix, and the groups of sub-matrix is itself a matrix. Applying Strassen algorithm recursively is therefore O(n^log2(7)) == O(n^2.8ish).
- adamnemecek 6y ago
  The article covers none of those.

bjeds 6y ago

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one out of many members in a family of notations that has a very specific mathematical definition, other common ones being small-o and big-theta. Analysis of algorithms is more difficult than it appears. If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance, for example. In such case you could talk of big-omega (your analysis is bounded-below instead of bounded-above, asymptotically).

bitexploder 6y ago
It is still a useful conceptual framework. Maybe this sparks someone’s interest. Agree it is much harder than it appears :)
nicoburns 6y ago
The problem with that is that informal use of big-o like notation is a lot more intuitive than the fancy language in your explanantion. Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.
- deleted 6y ago
  [deleted]
- sabas123 6y ago
  Why wouldn't you be able to just say "worst case n^2?"
  - smichel17 6y ago
    Dropping a constant

pmiller2 6y ago

Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significant amount of mathematical background. But, that definition isn't that hard. It's simply: f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). And, if you're in an analysis of algorithms context, it's even easier, because you typically don't have to worry about this absolute value business. Well, that M is essentially the reason you get to drop constant multiples of f(x). And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0. (No need to prove this, because this is what makes the "less significant" terms less significant.) I would also like to add that the equals sign in f(x) = O(g(x)) is one of the most useful abuses of notation that I know of, but it can be misleading. It doesn't behave at all like a real equality because it's not symmetric, but it is transitive and reflexive. It actually acts more like set membership than equality.

casion 6y ago
You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.
- roywiggins 6y ago
  The short version is that the fastest-growing term dominates all the others and for large xs the smaller terms round down to zero. Since big-O notation is about how the complexity grows for large inputs, you can assume the input is arbitrarily large, and you'll notice that the complexity is completely determined by the fastest-growing term. You drop the constant because it doesn't alter how the complexity grows as the input increases.
- pmiller2 6y ago
  Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite to assume for anyone who wants to be throwing around terms like "Big-O." If it's not too intrusive, may I ask what your graduate degrees are?

xyzelement 6y ago

It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.

windowojji 6y ago
> it's applied to a small enough input The whole point of big-O notation is to analyze algorithms as they're applied to input of size `n` larger than some `n_0`. Of course it's not useful for small inputs - it's explicitly about large inputs. > it's implemented very efficiently On large inputs, it's very hard see how, say, a linear algorithm with a quadratic algorithm regardless of how "efficiently" it's implemented. Assuming you're talking about something like cache friendliness or good register allocation?
- xyzelement 6y ago
  Yeah we are talking about the same thing. I agree that what you are saying is deeply connected to value of Big O. I am just pointing out that people sometimes forget to consider these things.
musingsole 6y ago
Most people jump to an extreme hyperbole instead of the reality what they're grappling with. Big-O is just that algorithmatised. Many software systems must be designed to anticipate orders of magnitude growth in scale. However, I'm not sure about how most software systems grow -- not sure anyone really knows. We all have narratives about it, but it's a small, small subset of projects I know about that have an order of magnitude different number of users than when I first learned about them (other than moving to effectively 0).
NationalPark 6y ago
Yes, it's good to remember that complexity analysis is only a theoretical topic that motivates certain approaches. When performance matters, you measure your program/system and use that as the ultimate guide for your work. Cache locality and branch prediction are two examples of practical issues that the theoretical approach will often ignore.

dragontamer 6y ago

Big O is literally easier than the analytical alternative. I didn't "understand" Big-O until I read Donald Knuth's "Art of Computer Programming". I forget exactly where Knuth does this... but Knuth derives the _exact_ number of average runtime on some algorithm. (Where "average" is defined as all possible permutations of the input). I forget why or where this derivation was, but it was along the lines of 3nlog(n) + 5n +25, or something along those lines (I made up the numbers). Solving for the specific and exact runtime of a function is very, very, very difficult. Instead of doing that, Comp. Sci has decided that the easier Big-O is "good enough" for most purposes. That's it. Big-O is ALWAYS easier to calculate than the exact runtime. Yeah, its still hard in some cases, and there are situations like Radix sort (O(n)) vs Quicksort (O(n*log(n)), or Karatsuba multiplication vs optimal multiplication (like O(n^1.5) vs O(n^1.4...)) where the "slower Big-O" is better in practice. But such situations are rare, and are easily figured out through profiling. --------- So lets do some real-talk. Most programmers don't wait on their code anymore. Computers are so fast, that all this algorithmic complexity is a red herring compared to other issues. By and large, inefficient programming languages are being used in grossly inefficient ways and no one cares. For most practical purposes, profiling with a stopwatch is your go-to methodology for analyzing algorithms. If that's not good enough, then profiling with a dedicated profiler (which can statistically count specific situations: like cache-hits or branch-mispredictions, as well as how many times any particular line of code ran). That's the information you want and need. Take the runtimes, plot it on a log-log plot, fit a growth-exponent on the curve and BAM, you got O(n^whatever). Where Big-O comes in are the situations where you're waiting for your code to finish. You run your code, and you wait 10-minutes, 1-hour, 10-hours, 2-days... will your code finish? Do you have an infinite loop? Or is it actually making forward progress? If so, how long do you estimate it to last? (And indeed: Hollywood movies are known to take multiple days to render a single frame, so these situations come up every now an then in practice). Under such a situation, you can't really run a profiler or use a stopwatch. You probably can run a big-O analysis by pen-and-paper over your code however, and then get an estimate on the size of your data. You'll want to make sure that you're O(n) or O(n*log(n)). If you're getting O(n^2) or O(n^3) from an algorithm that's taking days to run... you might be in trouble.

lrossi 6y ago

If you really want to make it easy to understand, make it graphical. That is: benchmark the code, varying the input size, and plot the results. Almost anyone should be able to understand. This might also reveal effects that are not taken into account by Big O notation, as not all algorithms that have the same complexity have the same performance. But I see it as a plus.

mhh__ 6y ago
The coefficients are what can bite you. Also amortized analysis, e.g. appending to a std::vector is O(n) in the worst case but O(1) almost all the time (the O(n) spikes come at something like every n = golden_ratio^k * initial size for integer k)
kevin_thibedeau 6y ago
It isn't uncommon for algorithms with "worse" algorithmic complexity to perform better than the faster alternative because the constant overhead of setting up the "better" algorithm eats all the performance gains. Sequential search is faster than binary search for short lists. You need to test to see where the crossover happens on your platform.
- kaba0 6y ago
  Not necessarily set-up time, but either constants can reverse the roles, or the fact that CPUs are hardly complex and the model most often used in analyzing algorithms is more simple and doesn’t map too well to things like caches, branch-prediction and the like.

axaxs 6y ago

I think a minimal reproduction of each common complexity would be a way more helpful addition. Someone with little math background is going to have no idea what log even means, much less what causes it.

alok-g 6y ago

>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?

mhh__ 6y ago
You'd need to know the exact details of the implementation of your arithmetic library, but it would depend on the integer in question which makes analysis a little harder so adding two numbers would become some function O(f(n, m)) where n, m are the two numbers or some property of them (length, digits etc.)
qsort 6y ago
It generally changes the analysis very little but makes it more annoying, which is why arithmetic is usually taken to be O(1). Formally speaking you'd have to specify a computational model to be able to talk about complexity (there is no such thing as 'complexity' but only 'complexity respective to a model'; e.g. you can change the big-O complexity on Turing machines by using more tapes). The computational model of a book like CLRS is "arithmetic is O(1), but we're not going to abuse that bug".
aweinstock 6y ago
The contrast between Gauss-Jordan[0] and the Bareiss algorithm[1] is a good example of explicitly handling the length of the numbers in bits as part of the runtime. Gauss-Jordan is O(n^3) if you consider addition and multiplication to be constant-time, but if it operates on arbitrary-precision integers, it can get exponentially slow[2]. The Bareiss algorithm avoids this worst-case behavior by choosing the pivots in a slightly more involved manner, which avoids building up large intermediate values. [0]: https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency https://en.wikipedia.org/wiki/Gaussian_elimination#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: https://staff.itee.uq.edu.au/havas/fh97.pdf https://staff.itee.uq.edu.au/havas/fh97.pdf, Section 3.1's "Construction A" is a specific matrix that exhibits the worst-case behavior.

infogulch 6y ago

I noticed some comments here discussing the right prerequisite knowledge to understand big-O and friends. I propose limits. I think it would be a lot easier for someone to understand how to think about big-O if they already understood limits. Lim [x -> inf] O(f(x))/O(g(x)) If you know limits, you know you how and why you can ignore all but the highest power term, how to compare and simplify other kinds of terms, etc. Though maybe that's too much to ask of someone new.

windowojji 6y ago
> Lim [x -> inf] O(f(x))/O(g(x)) I understand both limits and I've taught asymptotic analysis in the past. O(f(x)) and O(g(x)) are sets. How does one divide two sets? This explanation is ill formed.
psibi 6y ago
I don't think limits is a good way to understand it because of the reasons here: https://math.stackexchange.com/a/3222489/124772 https://math.stackexchange.com/a/3222489/124772

tracyhenry 6y ago

Remotely related: the Theory of Computation course I took (by Michael Sipser) gave me a more fundamental understanding of algorithmic complexity than I had through solving algorithmic puzzles in high-level languages: https://math.mit.edu/~sipser/18404/ https://math.mit.edu/~sipser/18404/

a_a_a_a 6y ago

lkjhlkjhlk

maweki 6y ago

What I always find a bit missing in such articles is what the n is. The author writes "If you consider "addition" to be 1 operation" and this seems kinda intuitive and is correct if we talk about normal machine integers. But adding two arbitrary integers might be somewhat linear in bit-width. And there we have it: with a fixed bit-width, this becomes a constant term. So you might not want to talk about number of input terms as n, but also width of your terms (and python integers are arbitrary precision btw.). So yeah, this is an upper bound on how many "steps" you do for every input, but often enough it's not really clear what a step is, especially if you have several "steps" that relate do different forms of data retrieval and organization (which often are culprits for bad performance if you're done optimizing the number of loops). Sometimes you can hide behind some guaruantees that your hashset has constant lookup. But did you factor in whether the hash function is actually constant (or even fast, for that matter)?

bnegreve 6y ago
> often enough it's not really clear what a step is The steps are basic CPU operations such as load/store and basic arithmetic operations performed on fixed width type. I.e. things a CPU can do. > And there we have it: with a fixed bit-width, this becomes a constant term. It makes sense because that is how the CPU works: arithmetic operations on fixed width types are performed in constant time in the CPU ALU. Adding anything below 2^32 requires the same number of cylces. It is only confusing when you confuse basic CPU operations with basic python instructions (an arbitrary precision addition is certainly not a simple operation from the cpu perspective)
- maweki 6y ago
  > The steps are basic CPU operations such as load/store Only if you consider the result of a comparison as a "store" into the register. But again, comparing two objects might not be constant. The compiler I develop for my PhD, for example, uses (written in Haskell) somewhat nested sets and quite a few operations are dominated by the equality check. > It is only confusing when you confuse basic CPU operations with basic python instructions But the author did exactly that, when they considered addition to be constant, which is a good approximation for small integers, but wrong in python. And really, you do have to consider those intricacies, that's why I chose this example, as sets and maps in python are basically hashmaps, you can assume constant lookup, for example, if your hash function works in constant time. And again, this begs the question what the n is. Usually we would set n as the number of items in a collection for its retrieval operation. But you actually also have to consider the item being retrieved.

tromp 6y ago

Note that f(n) = O(g(n)) denotes an asymptotic upper bound. So it would be correct (if confusing) to say that 2n+3 = O(n^2). This is important for use in algorithmic complexity because we may not always be able to determine the running time even up to a constant, but can more easily infer an upper bound. Using Omega instead denotes an asymptotic lower bound. To denote both, you use Theta: f(n) = Theta(g(n)) means that for two constants 0 < c1 < c2 and large enough n, we have c1 < f(n)/g(n) < c2. Finally, little o denotes vanishing behaviour. f(n) = o(g(n)) when f(n)/g(n) goes to 0 in the limit.

kaba0 6y ago
A nitpick because this is an accepted notation, but as others mentioned in the thread: when someone writes 2n+3 = O(n) they mean 2n+3 \in O(n) (\in is little epsilon in latex, that is “element of set”), since O(f) is the set of all functions that has “f as an upper bound”.

lordnacho 6y ago

The thing that didn't click for me was precisely the "try to count the operations" thing that the author mentions. In fact it's the wrong road to go down, it isn't the point of big-o, and yet that's how you're invited to think about it when the issue is presented in college. It's only natural to think "oh let's look at all the operations and add them up". I think of it pretty simply, but not in that formal big-theta/big-omega kind of way, because you want to just quickly have an idea of whether you'll write a really slow piece of code in general, not some best or worst case. The question is simply what growth model dominates the increase of time/space for the algo for each of the inputs? Imagine the algo is already processing millions of input A, and you now increase A by a factor of 10, 100, etc. This melts away all the setup costs, nothing machine specific like cache size matters, anything that isn't the dominating factor is swamped, and all you're left thinking about is probably how some loop expands. You also don't need to think about what coefficient that dominating term has, which you would if you tried to write an equation that took all the operations into account.

kaba0 6y ago
It was the contrary for me. I think it helps understanding that we are actually put a value to each line of code that gets executed, but instead of microbenchmarking, we do it in an abstract way, say print gets c1 constant, addition gets c2 and the like. For loops will multiply the instructions’ sum inside them by the number of times they get executed. And basically that’s it. You sum the whole thing and get something like (c1+c2)n+c3 for a for loop over an n element list or something with two instructions inside and one other outside the loop. Since these were arbitrary constants, c1 and c2 can be replaced by another one, so you’ve got cn+c3, and since (I’m not gonna be mathematically rigorous here) as n changes, it will be much larger than the others, we are only interested in it, hence it was an O(n) algorithm. The eye-opening thing about it was that for simple algorithms, I only need high-school math to analyze them for different measurements. Like, memory allocation is costly for this sort of application and I want to measure that, just count each malloc instead! (But do note that it is quite hard/impossible to rigorously analyze programs for modern CPUs with cache misses and the like)

breck 6y ago

One thought I’ve never had: “I wish I hadn’t been so much time thinking about Big O notation, power laws, and orders of magnitudes”

kadoban 6y ago

That in _no_ way explained big-O notation. It explained the basics of counting things to do with algorithms. Which is kind of fine, really. But why bother saying it's going to explain big-O?

joe_91 6y ago

Much better explained than in my computer science lectures! Nice simple examples. It's such an important topic to grasp too if you're going to end up working with software!

hisfastness 6y ago

Not a bad intro and appreciate the intention on keeping it short and simple, but personally for me I think Grokking Algorithms has the best beginner explanations of Big O and basic algorithms / data structures. If I had to share resources with a learner, I'd suggest Grokking as an item to go deeper on after reading this article.

deleted 6y ago

[deleted]

lamename 6y ago

Also a nice quick ref here https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/

ineedasername 6y ago

I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the moment "algorithms" we discussed in any learning material. Maybe it's just that it goes back to the common topic here on HN that there's a lot more inefficient code nowadays because faster processors & more memory helps to paper over the cracks. But if something like Big O isn't taught as one of the most primitive bits of knowledge in programming then I can't completely that trend either.

matttb 6y ago
Many, many developers did not go to school and have no 'CS' type learning
racl101 6y ago
I think this might be for the self taught crowd of developers who never formally took Comp Sci, yet, who are also wielding important positions in software development that pay as well if not more than the guys who did take comp sci. You'd be astounded how big this self taught cohort could be and how much power they wield. They do their job pretty well, and yet, the basics of computer science is something that they never learned. I met a senior guy the other day who had never heard of a freaking truth table for fuck's sake.
- jobbo 6y ago
  I was dropped into the tech lead position at my job last year; I started in game design at art college, so having to run and gun has been fascinating. I'd be lying if I said I wasn't scared reading about much of the stuff in this comment section that really should be bread and butter. I'm talking to my boss to see if there's some kind of training program I can pick-up on the side to help me gather what should be the basics that I've missed out on, although we're so overloaded finding the time and money is challenging. I'm lucky it's mostly CRUD, but I can't help by worry every architecture decision I'm making is going to cost us massively down the road.

analog31 6y ago

I learned a couple of things during a brief teaching stint. First, no matter how much math your students learned in their high school and college courses, you should expect to re-teach the concepts that are needed for your lesson. It needn't be extensive, but your students will thank you for it. Second, don't introduce more than one hard concept at once. Asymptotes can be reviewed with pure math functions such as polynomials, but that's as far as they got in high school math. Then there are the other "interesting" orders such as log(n) that can be introduced, and you can show graphically why they're useful. Now you're ready to discuss the order of algorithms. I'm not a computer scientist, but that's how I learned it, and while I don't remember all of the algorithms today, I still understand the derivations of their orders when I see them.

kodah 6y ago

I learned to code as a kid and only met mathematicians who consider themselves programmers as an adult. Some opinion, maybe unpopular: Big O notation can be quite informally understood by normal people. It is academic people that make it and keep it challenging because it is how they understand the world. This is why interviews have stayed materially gruesome despite loud voices wishing it weren't so. It's the language of the people that rule this industry and you either learn it or leave. That said, we can change it too, if we want.

asperous 6y ago
I have met a lot of programmers that don't know about the concept nor do they proactively think to apply it. I do understand the disconnect between knowing snobby language and doing good work. Certainly you can be an amazing programmer and apply these ideas possibly without ever even being trained on them or knowing the jargon. In industry at least, a lot of work is communication so you have to know what things are commonly called to explain your thoughts to other people. and along those lines Mathematicians are the ones that are studying this concept in the abstract, so its useful to use their lingo because then you know where to find all the abstract knowledge on the subject. Finally I'll say of all the obscure terminology for things intuitively applied, Big O has to be one of the most common, followed by gang of 4s design patterns.
- kodah 6y ago
  > In industry at least, a lot of work is communication so you have to know what things are commonly called to explain your thoughts to other people. and along those lines Mathematicians are the ones that are studying this concept in the abstract, so its useful to use their lingo because then you know where to find all the abstract knowledge on the subject. I think this is what I'm getting at. Mathematicians can adjust their language to communicate with a wider audience, especially on things as so commonly understood as Big O. It's a two way street, because you need to know and understand mathematical principles to be a good programmer, but if this is your only mode of understanding you are equally useless. There needs to be hiring gates for both.
rramadass 6y ago

ncmncm 6y ago

Big-O notation was the only thing taught to me in a college (tech) class that I use. Everything else I use, I had already learned; you can pick up everything CS departments teach, just by reading. Engineering wasn't like that. It was taught so well, by Paul Cull, that it seemed obvious and hardly in need of a name. But I wish I had a nickel for every time some hotshot thinks that, because they got the right big-O performance, they are done. Where performance matters, big-O is is table stakes. There is typically an order of magnitude or two to be gained from that point.

mypalmike 6y ago

As someone who learns best from experience, my intuition for algorithmic complexity didn't really come from reading about it or solving problems in CS classes (though that was useful). It came from running tests on my own inefficient code and waiting for it to finish, wondering why my stupid computer was frozen. And then digging in and realizing my O(n^3) or whatever algorithm was not going to be sufficiently fast for production cases.

codesparkle 6y ago

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

volkk 6y ago
Should also add that an inefficient solution for a mostly fixed input size is still going to be efficient. If you have to write a double for loop but the outer loop is iterating on a 1000 element array and the inner one is operating on a 26 element array (e.g alphabet), it's still a fast and probably good enough solution.
- gvx 6y ago
  Operating on a fixed size datatype is trivially O(1), too (because O(c) = O(1) when c is a constant).
rramadass 6y ago
Good caveat; beginners should not bother about any of this stuff. Focus on good modularity, clear code structure and language idioms and in general for readability.
chii 6y ago
And great programmers would knowingly solve a problem inefficiently, because it's easier to write and ship it to the customer, and thus prove that the problem being solved is valuable.
- blackbear_ 6y ago
  Until, two years layer, the program needs one minute to start, every operation needs ten seconds to be executed and nobody knows why the program needs gigs of ram to stay idle and what to do about it.
6y ago

deleted 6y ago

[deleted]

PhantomBKB 6y ago

I liked it, but perhaps giving an example each of the different complexities that it talks about with the suitable use case would have been great. On that note, I'll take up the task of doing that in the near future.

dfdz 6y ago

Disclaimer: I am very familiar with big O notation and find it intuitive. However, I think the notation \lesssim or << which is common in upper level math courses, but not often discussed in undergraduate texts is much easier to explain, and should be introduced in lower level courses. You write f(n) \lesssim g(n) if there is an absolute constant C such that f(n) \le C g(n) the meaning is completely clear and by rearranging an expression it can replace big O notation. For example instead of writing f(n) = g(n) + O(h(n)) you write |f(n) - g(n)| \lesssim h(n) https://math.stackexchange.com/questions/1793395/who-introduced-the-notation-lesssim https://math.stackexchange.com/questions/1793395/who-introdu...

gvx 6y ago
If I understand correctly, f(n) << g(n) is equivalent to f(n) = o(g(n)), not f(n) = O(g(n)).
- dfdz 6y ago
  It depends on the author/field. In analysis sometimes f(n) <<g(n) means f(n) = o(g(n)), but other times (especially in discrete math) f(n) << g(n) means f(n) = O(g(n)). Due to this ambiguity, I think the notation f(n) ~< g(n) or in latex f(n) \lesssim g(n) is more clear

WinterHoursTF 6y ago

I think calling it big O was a mistake. Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means.

ColFrancis 6y ago
Calling it big O is indeed a mistake (especially when you start using it with handwriting, o & O because difficult to distinguish). > Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means Tricky thing is, that's not what big O says. It's a statement about the asymptotic growth of a function which you can apply to a worst case. You'd be better off using "the worst case grows as at most". The distinction is important as you are ignoring two crucial things: the non-asymptotic behaviour and the coefficient of the asymptotic behaviour.
- WinterHoursTF 6y ago
  I know I was just talking about what people always seem to mean by big O. Also it is what O is applied on most of the time.

alisaus 6y ago

I was a really bad girl. Punish me with your dick in my mouth. - https://adultlove.life https://adultlove.life

dikaio 6y ago

Beautiful.