No, this is also inaccurate. Big-theta and average-case complexity are entirely different concepts. Big-O/theta/omega are all ways of categorizing functions. T

No, this is also inaccurate. Big-theta and average-case complexity are entirely different concepts. Big-O/theta/omega are all ways of categorizing functions. Those functions typically take as their argument some measure of the "size" of the input (which may be one variable or multiple). The output of the function could be: * worst-case performance ("largest possible running time for all inputs of size N") * average-case performance ("expected running time for an input of size N, chosen from some well-defined distribution") * amortized performance ("largest possible running time among all possible sequences of N inputs, divided by N") (We could also apply any of these definitions to something other than time, such as memory or I/O operations.) For any of these definitions, we can talk about big-O, or big-theta, or big-omega in a well-defined way. As an example, the worst-case time complexity of bubble sort is Ɵ(n^2). The average-case time complexity (assuming an input consisting of distinct elements, uniformly randomly permuted) is also Ɵ(n^2). Nevertheless, the best-case performance is Ɵ(n).