3 ms·

Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this

by yid 13y ago

Unfortunately, there are some misconceptions that are propagated in this article. Kudos on the effort, but some statements are just flat out wrong, such as this statement: "Big-O is all about the approximate worst-case performance". Big-O has nothing to do with worst-case, but is a bounding function. An O(n) algorithm is also O(n^2), O(2^n), etc. Those are valid bounds on the O(n) algorithm, just not the smallest.

baddox 13y ago
Note that there are other bounding functions, like bounded from the bottom (which still isn't the same thing as worst-case). See https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm.... Speaking of worst-case (or best-case, average-case, etc.) scenarios, how does big O notation relate? The variables inside an O() notation as far as I know refer only to the size of the input, so when we say that finding a value in an unsorted list is in O(n), we're referring to the worst-case scenario (obviously, finding a value in a list when that value is the head of the list is constant time, and not very interesting). Of course, that's a simplistic example, but with more complex algorithms like Quicksort, when we say it's in O(n log n) we're talking about average-case. Is this just because we know that worst-case performance in Quicksort is exceedingly rare so we don't bother mentioning that O(n log n) is average-case unless we're studying it more deeply?
- foobarbazqux 13y ago
  The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
  - baddox 13y ago
    Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
    - anonymoushn 13y ago
      It depends on context. Generally if people fail to specify, they mean average case, as in "Quicksort takes O(n*lg n) time". There may even be some amortization shenanigans thrown in there, as in "list.append takes O(1) time".
    - foobarbazqux 13y ago
      Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions. [1] https://mitpress.mit.edu/books/introduction-algorithms https://mitpress.mit.edu/books/introduction-algorithms (Introduction to Algorithms)
      - jfarmer 13y ago
        It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n } are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice? Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".
- mrbrowning 13y ago
  Big-O (or Ω or Θ) notation is orthogonal to notions of best-case or worst-case, which are merely constraints on the set of inputs we're considering. If, for example, you ask "what is the upper bound on best-case running time for linear search," then what you're actually asking is "given an input sequence that begins with the item being searched for, what is the upper bound on the running time." I think part of the confusion stems from the fact that when people supply bounds on best- or worst-case running times for deterministic algorithms, they often use Big-O notation when they're actually giving an asymptotically tight bound. So in the case of linear search's best case, O(1) is an upper bound, but the lower bound is of the same order, i.e. Ω(1). It's not incorrect, but it can be misleading. In the case of Quicksort, I think the answer to your question is yeah, pretty much. I mean, cases where you're dealing with nearly-sorted input are common in some domains and in that case you should be very much aware of the worst-case behavior of Quicksort, but otherwise I think the discussion from CLRS puts things in perspective: even if you had the bad luck of only ever receiving input sequences such that every partitioning led to a 99-to-1 split, then your running time is still going to be O(n lg n), since your recursion tree is going to be at most log-base-100/99(n) levels tall, which is the same as lg n / (lg 100/99), the denominator there being a constant factor that disappears in an asymptotic context.
- jfarmer 13y ago
  Here's an answer of mine on Quora you might find useful: https://www.quora.com/Algorithms/How-can-I-determine-whether-f-n-%CE%A9-g-n-f-n-theta-g-n-or-f-n-O-g-n-for-the-functions https://www.quora.com/Algorithms/How-can-I-determine-whether... There are two things going on. First, when we talk about Big-O we're not talking about the "worst case scenario." Big-O gives us an upper bound on the worst case scenario, but the actual worst case scenario might be better. Big-O means "no worse than" not "as bad as." When most people say Big-O they really mean Big-Θ, which does encapsulate the idea of "asymptotically equivalent, up to a constant." See my answer on Quora for more technical details. Second, Big-O and other forms of notation used in the asymptotic analysis of functions were invented before physical computers existed. They're statements about pure functions. When applied to the analysis of algorithms the function we're "really" analyzing isn't the algorithm. Rather, if we have an algorithm A that takes as its input a positive integer n, we're really analyzing the function "the length of time it takes algorithm A to run given input n." The up-to-a-constant nature of Big-O notation is nice because that constant can encapsulate things like processor speed, memory access times, and so forth. This enables us to make intelligent statements about algorithms per se without reference to the underlying machine on which the algorithm might be implemented. Even with ideal functions, this naïve asymptotic analysis has some problems. For a toy example, imagine a spiky function like this: f(n) = 800*n^2 if n is divisible by 1000000000 f(n) = 400*n otherwise This function is not O(n) but it is O(n^2). The "worst case" behaves like O(n^2), but for "most inputs" it behaves like O(n). We can't say "f(n) is asymptotically no worse than n, up to a constant" because for infinitely many inputs it is. Lots of algorithms behave like this in practice because we optimize for common cases perhaps at the expense of less common cases. "Common" is dictated by how our algorithm is used. Taking quicksort as an example, let's call the algorithm Q. We want to measure its running time given an input of length n. For input x, let's say it's running time is T(x). Well, there are many x such that len(x) == n, so what does it even mean to say "its running time given an input of length n?" Are we given a particular input of length n? A uniformly-selected-but-random input of length n? To the extent that we can, we want to be making statements about the algorithm per se, not statements about the algorithm given a particular input. On way to answer this to ask "Given an input of length n, what's the most time my algorithm could take?" In that case we're analyzing the following function: W(n) = max { T(x) | x is valid input and len(x) == n } On the other hand, maybe we care more about the average case. Perhaps we randomly pick 1,000 inputs of length n and average the running time. Now we're talking about something that looks more like a probability distribution than a discrete thing like "running time" because we've sampled the input space. And in fact, we could calculate "expected running time given input n" in this way and graph that. We could then make Big-O like statements about that new function, which is the kind of thing folks mean when they talk about "average case." Hope that helps!
pajju 13y ago
What you said is not very correct too! Big O tells about the "order of Growth of a function or the Growth rate", that's it. It gives a larger view of the function. Seeing from 1000 feet above the ground. Link: http://web.mit.edu/16.070/www/lecture/big_o.pdf http://web.mit.edu/16.070/www/lecture/big_o.pdf My understanding -- A bounding function is when we know the exact function and its end-points from an algorithm. We know the extremes. i.e C1 and C2. i.e a Function falls within that boundary, it will always stay within that box(end-points). C1 and C2 are 2 lines, making a rectangle. - Worst case, Best case, average case are different input cases, under which the algorithm grows in different ways. And we use BigO notation to classify them under easier functions, based on the order of Growth of a function. And unless we don't know that exact function, its not possible to predict for any input variables. So don't call Big O as any bounding function, unless we know c1 and c2 <end bounds>. - Big O is a notation that characterizes functions according to their growth rates. - Different functions with the same growth rate may be represented using the same O notation. - The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.
- yid 13y ago
  Nothing you've said contradicts anything I wrote. I mentioned bounding functions -- you've been a bit more pedantic, but essentially you've said nothing new.
fizz_and_buzz 13y ago
> An O(n) algorithm is also O(n^2), O(2^n), etc. To be fair, it is pretty common to be a little bit sloppy with this definition. People often say O(...) when they really mean Θ(...).
kazagistar 13y ago
While the mathematics use a bounding function, I am not sure how vital this is to a self taught programmer who is just trying to get insight into some algorithm.

by yid 13y ago

baddox 13y ago

Note that there are other bounding functions, like bounded from the bottom (which still isn't the same thing as worst-case). See https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm.... Speaking of worst-case (or best-case, average-case, etc.) scenarios, how does big O notation relate? The variables inside an O() notation as far as I know refer only to the size of the input, so when we say that finding a value in an unsorted list is in O(n), we're referring to the worst-case scenario (obviously, finding a value in a list when that value is the head of the list is constant time, and not very interesting). Of course, that's a simplistic example, but with more complex algorithms like Quicksort, when we say it's in O(n log n) we're talking about average-case. Is this just because we know that worst-case performance in Quicksort is exceedingly rare so we don't bother mentioning that O(n log n) is average-case unless we're studying it more deeply?

foobarbazqux 13y ago
The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.
- baddox 13y ago
  Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
  - anonymoushn 13y ago
    It depends on context. Generally if people fail to specify, they mean average case, as in "Quicksort takes O(n*lg n) time". There may even be some amortization shenanigans thrown in there, as in "list.append takes O(1) time".
  - foobarbazqux 13y ago
    Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions. [1] https://mitpress.mit.edu/books/introduction-algorithms https://mitpress.mit.edu/books/introduction-algorithms (Introduction to Algorithms)
    - jfarmer 13y ago
      It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n } are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice? Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".
mrbrowning 13y ago
Big-O (or Ω or Θ) notation is orthogonal to notions of best-case or worst-case, which are merely constraints on the set of inputs we're considering. If, for example, you ask "what is the upper bound on best-case running time for linear search," then what you're actually asking is "given an input sequence that begins with the item being searched for, what is the upper bound on the running time." I think part of the confusion stems from the fact that when people supply bounds on best- or worst-case running times for deterministic algorithms, they often use Big-O notation when they're actually giving an asymptotically tight bound. So in the case of linear search's best case, O(1) is an upper bound, but the lower bound is of the same order, i.e. Ω(1). It's not incorrect, but it can be misleading. In the case of Quicksort, I think the answer to your question is yeah, pretty much. I mean, cases where you're dealing with nearly-sorted input are common in some domains and in that case you should be very much aware of the worst-case behavior of Quicksort, but otherwise I think the discussion from CLRS puts things in perspective: even if you had the bad luck of only ever receiving input sequences such that every partitioning led to a 99-to-1 split, then your running time is still going to be O(n lg n), since your recursion tree is going to be at most log-base-100/99(n) levels tall, which is the same as lg n / (lg 100/99), the denominator there being a constant factor that disappears in an asymptotic context.
jfarmer 13y ago
Here's an answer of mine on Quora you might find useful: https://www.quora.com/Algorithms/How-can-I-determine-whether-f-n-%CE%A9-g-n-f-n-theta-g-n-or-f-n-O-g-n-for-the-functions https://www.quora.com/Algorithms/How-can-I-determine-whether... There are two things going on. First, when we talk about Big-O we're not talking about the "worst case scenario." Big-O gives us an upper bound on the worst case scenario, but the actual worst case scenario might be better. Big-O means "no worse than" not "as bad as." When most people say Big-O they really mean Big-Θ, which does encapsulate the idea of "asymptotically equivalent, up to a constant." See my answer on Quora for more technical details. Second, Big-O and other forms of notation used in the asymptotic analysis of functions were invented before physical computers existed. They're statements about pure functions. When applied to the analysis of algorithms the function we're "really" analyzing isn't the algorithm. Rather, if we have an algorithm A that takes as its input a positive integer n, we're really analyzing the function "the length of time it takes algorithm A to run given input n." The up-to-a-constant nature of Big-O notation is nice because that constant can encapsulate things like processor speed, memory access times, and so forth. This enables us to make intelligent statements about algorithms per se without reference to the underlying machine on which the algorithm might be implemented. Even with ideal functions, this naïve asymptotic analysis has some problems. For a toy example, imagine a spiky function like this: f(n) = 800*n^2 if n is divisible by 1000000000 f(n) = 400*n otherwise This function is not O(n) but it is O(n^2). The "worst case" behaves like O(n^2), but for "most inputs" it behaves like O(n). We can't say "f(n) is asymptotically no worse than n, up to a constant" because for infinitely many inputs it is. Lots of algorithms behave like this in practice because we optimize for common cases perhaps at the expense of less common cases. "Common" is dictated by how our algorithm is used. Taking quicksort as an example, let's call the algorithm Q. We want to measure its running time given an input of length n. For input x, let's say it's running time is T(x). Well, there are many x such that len(x) == n, so what does it even mean to say "its running time given an input of length n?" Are we given a particular input of length n? A uniformly-selected-but-random input of length n? To the extent that we can, we want to be making statements about the algorithm per se, not statements about the algorithm given a particular input. On way to answer this to ask "Given an input of length n, what's the most time my algorithm could take?" In that case we're analyzing the following function: W(n) = max { T(x) | x is valid input and len(x) == n } On the other hand, maybe we care more about the average case. Perhaps we randomly pick 1,000 inputs of length n and average the running time. Now we're talking about something that looks more like a probability distribution than a discrete thing like "running time" because we've sampled the input space. And in fact, we could calculate "expected running time given input n" in this way and graph that. We could then make Big-O like statements about that new function, which is the kind of thing folks mean when they talk about "average case." Hope that helps!

pajju 13y ago

What you said is not very correct too! Big O tells about the "order of Growth of a function or the Growth rate", that's it. It gives a larger view of the function. Seeing from 1000 feet above the ground. Link: http://web.mit.edu/16.070/www/lecture/big_o.pdf http://web.mit.edu/16.070/www/lecture/big_o.pdf My understanding -- A bounding function is when we know the exact function and its end-points from an algorithm. We know the extremes. i.e C1 and C2. i.e a Function falls within that boundary, it will always stay within that box(end-points). C1 and C2 are 2 lines, making a rectangle. - Worst case, Best case, average case are different input cases, under which the algorithm grows in different ways. And we use BigO notation to classify them under easier functions, based on the order of Growth of a function. And unless we don't know that exact function, its not possible to predict for any input variables. So don't call Big O as any bounding function, unless we know c1 and c2 <end bounds>. - Big O is a notation that characterizes functions according to their growth rates. - Different functions with the same growth rate may be represented using the same O notation. - The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

yid 13y ago
Nothing you've said contradicts anything I wrote. I mentioned bounding functions -- you've been a bit more pedantic, but essentially you've said nothing new.

fizz_and_buzz 13y ago

> An O(n) algorithm is also O(n^2), O(2^n), etc. To be fair, it is pretty common to be a little bit sloppy with this definition. People often say O(...) when they really mean Θ(...).

kazagistar 13y ago

While the mathematics use a bounding function, I am not sure how vital this is to a self taught programmer who is just trying to get insight into some algorithm.