Medium difficulty using Big-O notation

Question

In response to this question , debate began in the comments on the complexity of QuickSort. What I remember from my university time is that QuickSort is O(n^2) in the worst case, O(n log(n)) in the middle case, and O(n log(n)) (but with more tight binding) at best.

I need a correct mathematical explanation of the average complexity value to clearly explain what this means for those who think that a large O note can only be used for the worst case.

What I remember, if you determine the average complexity, you should consider the complexity of the algorithm for all possible inputs, calculate how many degenerate and normal cases. If the number of degenerate cases divided by n tends to 0 when n becomes large, then you can talk about the average complexity of the general function for normal cases.

Is this definition correct or is this definition of medium complexity different? And if that's right, can someone say it more strictly than me?

Answer 1

If you are looking for a formal definition, then:

Medium complexity is the expected runtime for random input.

Answer 2

You're right.

Big O (big theta, etc.) is used to measure functions. When you write f = O (g), it doesn't matter what the values ​​of f and g mean. This can be average time complexity, worst time complexity, spatial complexity, designation of the distribution of primes, etc.

The worst case complexity is a function that takes size n and tells you what maximum number of steps the algorithm sets to input size n.

The average value of complexity is a function that takes size n and tells you how many steps of the algorithm the input of size n sets.

As you can see, the complexity of the worst and medium cases are functions, so you can use big O to express your growth.

Answer 3

I think your definition is correct, but your conclusions are wrong.

It is not necessarily true that if the proportion of "bad" cases tends to 0, then the average complexity is equal to the complexity of the "normal" cases.

For example, suppose that 1 / (n ^ 2) cases are "bad" and the rest are "normal" and the "bad" cases take exactly (n ^ 4) operations, while the "normal" cases take exactly n operations.

Then the average number of operations required is:

 (n^4/n^2) + n(n^2-1)/(n^2) 

This function is O (n ^ 2), but not O (n).

In practice, however, you may find that time in all cases is polynomial, and the proportion of “bad” cases decreases exponentially. This is when you ignore the bad cases when calculating the average.

Answer 4

An average case analysis does the following:

Take all the inputs of a fixed length (say n ), summarize the entire working time of all instances of this length and create the middle one.

The problem is that you probably have to list all inputs of length n in order to come up with medium complexity.

Answer 5

Sending Big O Notation on Wikipedia :

Let f and g be two functions defined on a subset of real numbers. One writes f(x)=O(g(x)) as x --> infinity if ...

So, what is the prerequisite for the definition states is that the function f must take a number as input and give a number as output. What input number are we talking about? This is, presumably, a series of elements in the sequence to be sorted. What kind of output can we talk about? You can perform a series of operations to organize the sequence. But stop it. What is a function? Function on Wikipedia :

a function is the relationship between a set of inputs and a plurality of permissible outputs with the property that each input is associated with one output.

Are we ready to deduce one result with our preliminary estimate? No no. For a given sequence size, we can get a wide range of operations. Therefore, to ensure that the definition is applicable to our case, we need to reduce the set of possible results (the number of operations) to one value. This can be maximum ("worst case"), minimum ("best case") or medium.

The conclusion is that talking about the best / worst / average case is mathematically correct and using a large O record without those in the context of sorting complexity is somewhat messy.

On the other hand, we could be more precise and use the big Theta notation instead of the big O record.