5 ms·

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" bu

• 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
    • umanwizard 6y ago
      O(n^2) doesn’t necessarily mean worst case; it could mean average case.
  • deleted 6y ago
    [deleted]
• Edmond 6y ago
  Agreed. The use of "Big O Notation" itself as a way of referring to algorithmic complexity seems like a misnomer, considering that the topic is about analysis rather than the notation used to express the results of such analysis. Unfortunately academic textbooks have terrible "UX", so students end up dealing with confusing presentation of topics, hence we're stuck with labels such as "Big O Notation".
  • bjeds 6y ago
    I hear you. Whether I like it or not, by now big o notation has fallen into the category of "folklore" that working engineers use and abuse informally without being very precise about it. It's like the "proof by engineers induction": if some statement P(n) is true for P(0), P(1) and P(2), then P(n) is true for all n \in Z. :-) Similarly if an engineer states that algorithm has a runtime of O(f(n)) that should probably be read as "as n grows very large (whatever that means) the runtime approximates (whatever that means) some bound (below, above, whatever) f(n). yolo.". But people should at least be _aware_ that they are being imprecise about it. If I read a blog post or StackOverflow post or whatever and I see big-theta notation I know that the person is probably precise with her definition. If I see big-o then it may be correct, or accidentally correct (happens often due to the nature of the definition) or mistaken.
    • tshaddox 6y ago
      There can be appropriate levels of imprecision. Arguably all communication necessarily requires that. This is only a problem if it leads to an unnoticed miscommunication. For example, I suspect most of the time when an engineers refers to an algorithm as being in O(n^2) they intend to preclude the possibility that the algorithm is not in O(n).
      • bonzini 6y ago
        Usually "average" or worst case" O(n^2) means it's really big O, while "best case" or "always" O(n log n) means big Theta.
• cgriswald 6y ago
  For Python code, I usually just ask critics if they’ve tested it (because I have). Frequently using a built-in will be faster than a custom loop even if at the surface level you’re going over the data more than once.
  • mhh__ 6y ago
    Anecdotally (it was a contrived sorting benchmark so the exact numbers don't really matter), Python started off about 3 times slower than D, but and grew at what would be considered the same O() but the coefficient was enormous. To the point where a D was taking 3s for n-million arrays, Python closer to one minute. Node was actually very impressive, roughly as fast as D's reference compiler (cutting edge optimisations maybe 2 decades ago) in release mode.
• sixstringtheory 6y ago
  > 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 If a language/library can change the dominant asymptotic term of an algorithm like that, instead of just the constant factor, that is a problem. Does that really happen with python or is this exaggeration? I’m inclined to accept another reason to dislike these super high level interpreted langs but I’ve never seen something that e.g. appears written to be logarithmic to become quadratic because of library implementation details.
  • Brian_K_White 6y ago
    The language doesn't matter, nor even it's high vs low class. You can write a short function in any language that looks O(1) if you only look at the surface or high level of it. Even assembly. Meanwhile in the middle of that routine is a single call to another function or macro which may be 0(1) or O(n!). Python was just an example.
    • a1369209993 6y ago
      > Even assembly. Although high-level languages like python or to a lesser but less excusable degree C++ are more susceptible to this because more features can secretly be greater-than-constant-time function calls.
• tester756 6y ago
  >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). Of course, that's why Big O says one thing, Compiler, CPU and Caches may say the other.
• zachrose 6y ago
  I appreciate that the author was specific about “if you count addition as 1 operation.” Without saying this, it’s not obvious that the notation is such a simplified abstraction over operations and their costs, with all the limitations that come with that simplification.
• bakuninsbart 6y ago
  Exactly, the link above starts well, but fails in some regards. If you use big O, you should give the mathematical definition and at least shortly explain it. The idea of an upper boundary isn't very hard, and it is actually important to understand that an algorithm running in O(n) is also running in O(n log(n)) is also running in O(n^2). It is at least necessary to understand the other greek letters, which really does come in handy in a deeper understanding of algorithms. The list of "common" O's is also kinda bad. Particularly, and I see this all the time, I think it is a mistake to go from O(n^2) to O(c^n), as this is the step that leaves polynomial time complexity, and glosses over the fact, that each level of exponent constitutes a different time complexity. Here the mathematical notation of O(n^2), O(n^3), ..., O(n^l) is indispensible. Nesting loops is probably one of the most commonly relevant applications of O-notations, so this actually has an influence on real-world implementations.
• melenaboija 6y ago
  I agree with what you say and not a Python fanatic but this high level language stigmas catch my attention. If you try to implement your own, let's say, intersection of sets you will probably get at most the same performance as Python using a reasonable amount of time. I guess my point is that seeing the comment of Python in a thread like this can also be confusing. Bad (or maybe I should say "not appropriate for your use") implementations can exist in any language.
• cortesoft 6y ago
  I think the main purpose of an “explained as easily as possible” article is to help the reader understand when SOMEONE ELSE uses the term. Sure, I can choose t use informal language, but I can’t stop someone else from using big o notation when speaking to me or writing something I want to read.
• indymike 6y ago
  I didn't really read that article as being for a developer. I read it and thought, hey, this one would be good to share with a few project managers & business unit managers. Any time people who are not programmers (especially ones we have to work with) start to better understand what we're really doing, it is a good thing. Articles like this are superb for helping them understand that developers do have a disciplined and rigorous way of solving problems. I do agree with you that these articles do leave a lot of detail and precision out. They tend to give the reader a superficial understanding of the subject... but a superficial understanding may be enough to help.
• Al-Khwarizmi 6y ago
  I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts. I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like readers of this piece, it's enough and it's not worth being fussy about it. What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.
  • repsilat 6y ago
    > even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases" Just to be careful here: the difference between big/little oh/theta/omega is orthogonal to best/worst/average case. A pedant could say that merge sort makes O(n^3) comparisons in both the best and worst case, ω(1) in both the best and worst case, etc. Colloquially, the former means "as fast as", and the latter means "slower than".
    • gvx 6y ago
      I've seen this a lot, where people are convinced big Oh is specifically meant for worst cases performance. And there may be some logic behind it, because if some function is in Θ(n^3) in the worst case, then it is true that it is in O(n^3) in all cases, so maybe that is why they couple big Oh with worst case growth.
      • Al-Khwarizmi 6y ago
        Again, I think from a shallow perspective it makes sense. If an algorithm always runs in O(n^3), then it's guaranteed that it runs in O(n^3) in the worst case. And if an algorithm runs in O(n^3) in the worst case, then it's guaranteed to always run in O(n^3) (but not in Θ(n^3), of course). So if you only care about worst-case performance, it's reasonable to only use the big O. Of course, what your parent comment says is also true - you could say that mergesort is O(2^n), in the worst case or in any other case, and be correct because it's an upper bound. But people using Big Oh informally don't say that because you typically want to show how good your algorithm is, so you use the tightest upper bound possible (i.e. the big theta of the worst case).
• polishdude20 6y ago
  Can you recommend any good algorithms books?
  • bhrgunatha 6y ago
    I'm assuming you want something rigorous - based on the comment you replies to. Many people will recommend CLRS [0] but I prefer it as a reference, rather than a learning resource. I feel it's very dry and academic. Instead I'd recommend Tim Roughgarden's series of books Algorithms Illuminated for learning about analysis and algorithms. He also has courses on Coursera and Edx to cover the material. It's thorough rigorous and shows algorithms that apply to different paradigms - lke divide and conquer, graph theory. Sedgewick and Wayne's Algorithms has a companion website with lots of additional material (heavily Java based) - and courses on Coursera too. Again I think it's more approachable than CLRS while still being detailed and covering the theory. [1] https://mitpress.mit.edu/books/introduction-algorithms-third-edition https://mitpress.mit.edu/books/introduction-algorithms-third... [2] http://timroughgarden.org/books.html http://timroughgarden.org/books.html [3] https://algs4.cs.princeton.edu/home/ https://algs4.cs.princeton.edu/home/
    • polishdude20 6y ago
      Thanks!
• kristopolous 6y ago
  Last summer I was interviewing at a FAANG company for a supposed senior level position and I pointed this out. Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. It was enormously frustrating, especially when I demonstrated real world runtime to the interviewer of two implementations. If they need someone to actually make things work well on real physical hardware, they need to know how the claims map to the physical reality and the fundamental limitations of chalkboard optimization. The real world actually matters. If he knew this maybe he wouldn't be overbudget, overdeadline and trying to mad hire people like some parody of the mythical man month... 8 months later it still rubs me the wrong way - that is, a bad faith read on new information as obviously objectively wrong and the speaker (me) as misinformed even after it's been demonstrated as accurate. Assuming everyone is stupid is a great way to hire, just fantastic. I'd bet thousands the project is either still off the rails or they've overhauled the org chart. The product hasn't been publicly announced yet btw. It's really all for the best. This way I only wasted one day instead of say 6 additional months just spinning wheels against a stonewall.
  • iujjkfjdkkdkf 6y ago
    > Instead I was treated as if I fundamentally had no understanding of algorithms whatsoever. This and similar experiences, basically discovering the interviewer, potential boss, or worse, actual boss, is not a colleague but actually a shallow copy of what one would expect from someone in their role, is pretty common, especially (from what I've seen) in orgs with a clear divide between a "manager" class that is mostly composed of people with less experience than those they are managing, and those doing the work. It's best, as you say, to just write off the time wasted on the discussion, move on, and be happy you don't have to work with them.
  • leonidasv 6y ago
    Big O is not about actual hardware, not it should be. We can argue about it being useful or not, but that don't change this fact.
    • kristopolous 6y ago
• proverbialbunny 6y ago
  >The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation If the point is to identify the speed (or ram consumption) of algorithm, then why not check for that itself instead of the vocabulary in an interview? Why be pedantic when you can instead measure how well they would do as a developer? In an interview you can ask followup questions to see how precise their ability to explain their thought process is. If someone is so pedantic that they would consider the interviewee to have shot themselves in the foot because they said "The big O is n squared." without any followup questions from the interviewer, that doesn't sound healthy to me. I would worry this kind of culture would extend past the interview and it wouldn't be an enjoyable place to work. Can you imagine working in a place where people regularly argue over terminology instead of just making sure everyone is on the same page? (Full warning: I'm not a dev, so I'm coming in from the view of another industry.)
  • pvg 6y ago
    If the point is to identify the speed (or ram consumption) of algorithm, then why not check for that itself instead of the vocabulary To some extent because the "that itself" is a deep field in its own right with its own specialized vocabulary.
• d0mine 6y ago
  > 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 How does it change big O? Typically, you implement "bignum" on top of "hardware integer" regardless of the language. Or do you mean that some common integer operations are implemented with suboptimal big O in CPython?
  • crashocaster 6y ago
    For some large n, integers in the algorithm may be so large that operations on them cease to be constant time.
    • d0mine 6y ago
      that is obvious. But how does it change big O? (why any manual implementation would have a better big O compared to existing arithmetics implementation in CPython?)
      • kaba0 6y ago
        I think he meant that naively implementing an algorithm may not be bounded by the O notation he/she originally wanted due to code calling other functions “hidden” from the programmer.