4 ms·

Theta(X) is not "average case" behaviour, it means "both Omega(X) and O(X)". Ex: merge sort is Theta(n log(n)), but quick sort is not. The author is likely sa

Theta(X) is not "average case" behaviour, it means "both Omega(X) and O(X)". Ex: merge sort is Theta(n log(n)), but quick sort is not. The author is likely saying "worst case O(n log(n))" as redundancy to emphasize that this is worst case behaviour.

tsimionescu 5y ago
It's not redundant. You can have "average case O(n log(n))" but "worse case O(n^2)", like quicksort does. Depending on the pivot function, that "worse case" can be more or less common.
- karpierz 5y ago
  It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). But colloquially, it means that the average number of operations over all possible inputs on length n is X. It is redundant to say "worst case O(n^2)". By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
  - Kranar 5y ago
    You are incorrect about this. Worst case and Big O are independent of one another. The O, Ω, Θ, etc... are about describing bounds where O(f) is used for the set of asymptotic upper bounds on f, Ω(f) is the set of asymptotic lower bounds on f, and Θ(f) is the intersection of O(f) and Ω(f). Typically f is used to describe space or time complexity of an algorithm, but it can be used for any function that maps positive integers to the non-negative real numbers. You can make any combination of best case/worst case/average case with O, Ω, Θ. In fact, you can even consider other cases as well such as amortized cases, 90th percentile cases, any case you want to investigate that can be defined as a function from positive integers to non-negative real numbers can be classified as having an asymptotic upper bound, lower bound, or tight bound.
    - karpierz 5y ago
      Yeah, okay. You are correct here. "Average-case of algorithm X" can be a function function (average number of operations for all possible inputs of length n). And asymptotic bounds can be applied to arbitrary functions from R -> R.
  - tsimionescu 5y ago
    > It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). You are wrong. It is perfectly formally correct to say "average case complexity is 2n log(100n) + 78n + 90, which is O(n log (n))". > By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X. No, that is, in fact, a colloquial use of O(X). O(X), formally, is simply the set of all functions that are bigger than X up to some constant factor. It has nothing to do with number of operations in itself. Instead, we formally define complexity functions for an algorithm, which are the minimum/average/maximum number of operations the algorithm will execute for any input of size N; call these functions Cmin(n), Cavg(n), Cmax(n). Then, we can say that C_(n) is in O(X(n)) (or, as a shorthand, C_(n) = O(X(n))) if there exists a number k such that C_(n) < k * X(n) for any n > n0. So, we can say that the best case complexity of an algorithm, Cmin(n), is O(n^2); this means that even for the best possible input of length n, it will execute at least k * n^2 steps, for some k. Or, we can say that the worse case complexity of some algorithm, Cmax(n), is Omega(n^2); that is, that even in the worse case input of length n, it will execute less than k * n^2 steps, for some k. In fact, the concept "number of steps that an algorithm will execute for any input of size n" is not a mathematical function at all (unlike min/max/avg number of steps), since there isn't, in general, a unique such number for any given size. So, I would argue that saying "complexity O(n^2)" is in fact ill-defined formally, and that, if you want to be formal, you must specify "worst case complexity O(n^2)".
    - stonemetal12 5y ago
      Would argue it isn't perfectly formally correct, because "average case complexity" isn't well defined. Is average here mean, median or mode? It is typically used as if it meant, 90th percentile, or all but a few degenerate cases. But that is a bit nit picky.
      - naniwaduni 5y ago
        I'm not sure I've ever seen anyone argue over which measure of central tendency to use to assess the "average case". You certainly could, but it doesn't strike me as a particularly productive argument; in common parlance, an average is essentially always either an arithmetic mean or a non-rigorous informal typical case unless otherwise specified; it also normally doesn't matter very much since most algorithms of interest do have their complexity distributed across inputs s.t. as input size goes to infinity one regime describes the behavior on almost all inputs. It's surprisingly hard to even come up with one without just having having an approximately constant fraction of inputs just be trivial cases. The much more important problem with "average case" complexity, particularly infamously for sorts, is just that practical "typical" inputs aren't distributed evenly over the space of possible inputs; pathological inputs have, after all, practically by definition, a nontrivial almost–computable property that informally gives them more of a reason to exist than than the average input.

tsimionescu 5y ago

It's not redundant. You can have "average case O(n log(n))" but "worse case O(n^2)", like quicksort does. Depending on the pivot function, that "worse case" can be more or less common.

karpierz 5y ago
It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). But colloquially, it means that the average number of operations over all possible inputs on length n is X. It is redundant to say "worst case O(n^2)". By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
- Kranar 5y ago
  You are incorrect about this. Worst case and Big O are independent of one another. The O, Ω, Θ, etc... are about describing bounds where O(f) is used for the set of asymptotic upper bounds on f, Ω(f) is the set of asymptotic lower bounds on f, and Θ(f) is the intersection of O(f) and Ω(f). Typically f is used to describe space or time complexity of an algorithm, but it can be used for any function that maps positive integers to the non-negative real numbers. You can make any combination of best case/worst case/average case with O, Ω, Θ. In fact, you can even consider other cases as well such as amortized cases, 90th percentile cases, any case you want to investigate that can be defined as a function from positive integers to non-negative real numbers can be classified as having an asymptotic upper bound, lower bound, or tight bound.
  - karpierz 5y ago
    Yeah, okay. You are correct here. "Average-case of algorithm X" can be a function function (average number of operations for all possible inputs of length n). And asymptotic bounds can be applied to arbitrary functions from R -> R.
- tsimionescu 5y ago
  > It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O(). You are wrong. It is perfectly formally correct to say "average case complexity is 2n log(100n) + 78n + 90, which is O(n log (n))". > By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X. No, that is, in fact, a colloquial use of O(X). O(X), formally, is simply the set of all functions that are bigger than X up to some constant factor. It has nothing to do with number of operations in itself. Instead, we formally define complexity functions for an algorithm, which are the minimum/average/maximum number of operations the algorithm will execute for any input of size N; call these functions Cmin(n), Cavg(n), Cmax(n). Then, we can say that C_(n) is in O(X(n)) (or, as a shorthand, C_(n) = O(X(n))) if there exists a number k such that C_(n) < k * X(n) for any n > n0. So, we can say that the best case complexity of an algorithm, Cmin(n), is O(n^2); this means that even for the best possible input of length n, it will execute at least k * n^2 steps, for some k. Or, we can say that the worse case complexity of some algorithm, Cmax(n), is Omega(n^2); that is, that even in the worse case input of length n, it will execute less than k * n^2 steps, for some k. In fact, the concept "number of steps that an algorithm will execute for any input of size n" is not a mathematical function at all (unlike min/max/avg number of steps), since there isn't, in general, a unique such number for any given size. So, I would argue that saying "complexity O(n^2)" is in fact ill-defined formally, and that, if you want to be formal, you must specify "worst case complexity O(n^2)".
  - stonemetal12 5y ago
    Would argue it isn't perfectly formally correct, because "average case complexity" isn't well defined. Is average here mean, median or mode? It is typically used as if it meant, 90th percentile, or all but a few degenerate cases. But that is a bit nit picky.
    - naniwaduni 5y ago
      I'm not sure I've ever seen anyone argue over which measure of central tendency to use to assess the "average case". You certainly could, but it doesn't strike me as a particularly productive argument; in common parlance, an average is essentially always either an arithmetic mean or a non-rigorous informal typical case unless otherwise specified; it also normally doesn't matter very much since most algorithms of interest do have their complexity distributed across inputs s.t. as input size goes to infinity one regime describes the behavior on almost all inputs. It's surprisingly hard to even come up with one without just having having an approximately constant fraction of inputs just be trivial cases. The much more important problem with "average case" complexity, particularly infamously for sorts, is just that practical "typical" inputs aren't distributed evenly over the space of possible inputs; pathological inputs have, after all, practically by definition, a nontrivial almost–computable property that informally gives them more of a reason to exist than than the average input.