4 ms·

Having gone through electrical engineering, I always felt that Big O notation was never properly explained unless I happened to miss every time it was introduce

• daemonologist 1y ago
  My university had an "algorithm analysis" class (required for CS majors) which covered it along with various kinds of proofs. That was a junior/senior year class though; I think it was really expected that you were already somewhat familiar with the concept by the end of your first year (via osmosis I guess).
• leni536 1y ago
  A function f(x) is said to be O(g(x)) if f(x)/g(x) is bounded, that is there is some C so that for every x, f(x)/g(x) < C . In computer science f(x) is often some complexity function, like number of some specific operations when running an algorithm to completion.
  • mvdtnz 1y ago
    What an asshole way of explaining it. For practical purposes (don't @ me if this is technically wrong, I don't give a shit) it's a description of how the cost of an algorithm grows with the size of the input. For example if the cost doubles every time the input increments then it's O(n^2). If the cost increases in step with the input size then it's O(n). Simples.
    • lern_too_spel 1y ago
      If the cost doubles for each increment in the input size, it's O(2^n).
      • mvdtnz 1y ago
        Right you are, my bad.
    • tauroid 1y ago
      Okay unless you're doing numerical analysis where they use it for the growth rate of the error term, which has nothing to do with cost or algorithms
    • badosu 1y ago
      I don't have a computer science education, but I had a math one. I found it a great explanation, but I understand why others would feel it's not. It definitely is not an "asshole" way of explaining it though.
    • xigoi 1y ago
      This is not only “technically” wrong, but completely wrong. O-notation has absolutely nothing to do with algorithms.
      • writebetterc 1y ago
        Let's not over correct, of course O-notation has something do with algorithms for the working programmer.
  • blt 1y ago
    This needs to be refined: f(x) is O(g(x)) if there exists some X >= 0 such that f(x)/g(x) is bounded for all x > X. Otherwise, we cannot say that 1 is O(x), for example.
• bongodongobob 1y ago
  Comp sci 101. Learned it my first year. There really isn't anything to it. It just describes how the number of operations grow as the number of inputs in your algorithm increases. It looks scary, but it's very simple and straightforward.
  • nwatson 1y ago
    It can get a lot more complicated though. At times there are more parameters to an algorithm's complexity than just `n`. E.g., the parameters for big-O might be `n`, `K`, and `ρ`, and some expressions in the big-O might involve combinations of those parameters. In such cases as well, one might know for a specific application of the algorithm that, for example, `ρ` is bounded, and so the big-O becomes more influenced by the `n` and `K`.
    • bongodongobob 1y ago
      Yeah that's fair. Calc 1 should be enough to understand that.
  • Sankozi 1y ago
    You are commenting under blog post that tried to explain it and got it wrong. It is not simple. Examples: - algorithm with O(2^n) complexity might be faster for your problem than O(1) algorithm - the same algorithm may be O(2^n) or O(n³) depending how you define size function This is not straightforward.
    • bongodongobob 1y ago
      It is though.
    • fxwin 1y ago
      that's why he said it describes how runtime behaves as input size changes, not how it behaves for specific values
• LPisGood 1y ago
  That’s because you could define it in a lot of different ways. For example, if you define it as the number of steps it takes some Turing machine representing some algorithm to halt, then there is no such thing as a logarithmic time algorithm; O(lg n) = O(1)
  • School-Cotton 1y ago
    Why is that?
    • LPisGood 1y ago
      Log(n) grows slower than n. That means there is some number N where the process terminates in fewer than N state transitions. But in a Turing machine, you can read at most one new cell on the tape with each state transition. Therefore the algorithm halts in constant time.
      • Droobfest 1y ago
        What is the relationship between n and N? log(n) is still unbounded so I can’t make sense of your comment.
        • LPisGood 1y ago
          There is no relationship between n and N, of course. N is some fixed constant. Log(n) is unbounded, yes, but if a Turing machine halts in sub-linear time then there is some length input for which that TM halts before it reads every cell of the input tape. Therefore, it doesn’t matter how the size of the input grows, that TM must halt in constant time. Make sense?
          • Droobfest 1y ago
            I’m sorry but no. Maybe it’s my ignorance of TM’s, but O(log n) doesn’t read all input by definition. It doesn’t follow that it is therefore _independent_ of the input size. What makes a/your TM special that this is the case? I don’t mean to take too much of your time though, maybe I’m too dumb for this. Edit: I can sort of see how O(log n) is impossible or at least O(n) in a TM, but to reduce it to O(1) makes no sense to me
• jayd16 1y ago
  The Discrete Math class in the CS track is where I got the bulk of it.
• ordu 1y ago
  > It always felt like it was just hand waived as something we should already know. I learned about Big O notation while learning calculus, along with little-o.
• anthomtb 1y ago
  Big O was introduced in my Data Structures and Algorithms (DSA) class which was nominally a second year undergrad class. In practice, most Computer Science (CS) students were far enough advanced to take DSA in their first year. I took DSA as a third-year Electrical and Computer Engineering student. I recall maybe 15 minutes of exposition on the topic and exam questions of a near-throwaway nature (ergo: write this tree parsing algorithm, 95 points for your code's correctness, 5 points for explaining your algorithm's Big O complexity). It did seem like something that CS professors and teaching assistants considered either trivial or self-explanatory.