6 ms·

> What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it

by c3534l 8y ago

> What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). You're conflating theta and omega notation for big O. Big O is the worst case scenario. The average or even typical operation doesn't matter. If the algorithm is the most complex when sorting a list of items that were already sorted in descending order, then that is the use-case that is considered when figuring out Big O. If you want average, use Big theta.

teraflop 8y ago
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).
edflsafoiewq 8y ago
No, you're conflating Big O measuring an asymptotic upper bound of a function with worst-case analysis measuring the upper bound of resource use. These are different things. Asymptotic notation is totally oblivious to what is being measured, whether its a worst-case or average-case or anything else. You can give the Big O of the best case, the Big Theta of the worst case, etc.
roel_v 8y ago
Fair enough, when looking at the academic origin and defintions; but googling a bit and looking at articles like https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%89-big-%CE%B8-aa259ae8a1c2 https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%8... (under 'The Big Caveat', third paragraph), I feel validated in my assertion that your 'Big theta' is what is in practice and colloquially is known as 'Big O', and is also what this article is talking about. (But I'll admit that I had mostly forgotten about this distinction, and certainly couldn't tell which one is which without looking it up)
umanwizard 8y ago
Best, average, and worst case (and any other mathematical function from an ordered set to another ordered set) can all be described with big omega, theta, and O notation. The two concepts are orthogonal. For example: Quicksort's average-case time complexity is Omega(1), also Omega(n log(n)), Theta(n log(n)), O(n log(n)), and also O(e^n). Its worst-case time complexity is Omega(1), also Omega(n^2), Theta(n^2), O(n^2), and also O(e^n).

by c3534l 8y ago

teraflop 8y ago

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).

edflsafoiewq 8y ago

No, you're conflating Big O measuring an asymptotic upper bound of a function with worst-case analysis measuring the upper bound of resource use. These are different things. Asymptotic notation is totally oblivious to what is being measured, whether its a worst-case or average-case or anything else. You can give the Big O of the best case, the Big Theta of the worst case, etc.

roel_v 8y ago

Fair enough, when looking at the academic origin and defintions; but googling a bit and looking at articles like https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%89-big-%CE%B8-aa259ae8a1c2 https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%8... (under 'The Big Caveat', third paragraph), I feel validated in my assertion that your 'Big theta' is what is in practice and colloquially is known as 'Big O', and is also what this article is talking about. (But I'll admit that I had mostly forgotten about this distinction, and certainly couldn't tell which one is which without looking it up)

umanwizard 8y ago

Best, average, and worst case (and any other mathematical function from an ordered set to another ordered set) can all be described with big omega, theta, and O notation. The two concepts are orthogonal. For example: Quicksort's average-case time complexity is Omega(1), also Omega(n log(n)), Theta(n log(n)), O(n log(n)), and also O(e^n). Its worst-case time complexity is Omega(1), also Omega(n^2), Theta(n^2), O(n^2), and also O(e^n).