Data Structures and Algorithms (H) Lecture 6 Notes

Randomization and Lower Bounds

A Randomized Version of QuickSort

Choosing the right pivot element can be tricky since we have no idea a priori which element can be a good pivot. A (surprisingly good) solution is to leave it to chance:

Performance of Randomized-QuickSort

First we assume that in the following that all elements in the array are distinct. Now we may ask: what is a worst-case input for Randomized-QuickSort? The answer is that there is no worst case for Randomized-QuickSort! The reason behind this is simple: all inputs lead to the same runtime behavior. - The -th smallest element is chosen with uniform probability. - Every split is equally likely, regardless of the input. - The runtime is random, but the random process (probability distribution) is the same for every input.

Runtime of Randomized Algorithms

For randomized algorithms (in contrast to deterministic algorithms) we consider the expected running time .

Tip

For more information on expectations, random variables, and probabilities, see the notes for STA219 Probability and Statistics for Engineering.

For analyzing sorting algorithms the number of comparisons of elements made is an interesting quantity:

• For QuickSort and other algorithms it can be used as a proxy or substitute for the overall running time.
  • Analyzing the number of comparisons might be easier than analyzing the number of elementary operations.
• Comparisons can be costly if the keys to be compared are not numbers, but more complex object.
• Algorithms making fewer comparisons might be preferable, even if the overall runtime is the same.
• There is a lower bound for the running time of all sorting algorithms that rely on comparisons only.

Let be the number of comparisons of elements made by QuickSort. Since comparisons are elementary operations, .

For each comparison QuickSort only makes other operations in the for loop. So other operations sum to . Hence we have and thus and we need to show So we can analyze the number of operations as a substitute for the runtime in the RAM model.

Expected Time for Randomized-QuickSort

Theorem

The expected number of comparisons of Randomized-QuickSort is for every input where all elements are distinct.

Proof. for ease of analysis, rename array elements to with , i.e.  is the -th smallest element.

A key observation is that each pair of elements is compared at most once. The reason is that elements are only compared against the pivot, and after Partition ends the pivot is never touched again.

Let be the number of times and are compared: Then the total number of comparisons is Taking expectations on both sides and using linearity of expectations gives us is compared against when:

• If pivot is or then the decision whether to compare is postponed to a recursive call.
• If pivot is or , then they are compared.
• If pivot is then and become separated and are never compared.

A decision is only made if . So and are only compared if the first pivot chosen amongst is either or . Since gthese are values, out of which 2 lead to being compared. And since the pivot element is chosen uniformly at random, we have Substitute this back into the expectation expression, we have: Substituting yields

Random Input vs. Randomized Algorithm

QuickSort is efficient if:

• The input is random or
• the pivot element is chosen randomly.

Key Insight

We have no control over the former, but we can make the latter happen.

• Deterministic QuickSort
  • Pro: the runtime is deeterministic for each input
  • Con: may be inefficient on some inputs
• Randomized QuickSort
  • Pro: same behavior on all inputs
  • Con: runtime is random, running it twice gives different times

Other Applications of Randomization

• Random Sampling
  • Great for big data
  • Sample likely reflects properties of the set it is taken from
• Symmetry breaking
  • Vital for many distributed algorithms
• Randomized search heuristics
  • General-purpose optimizers, great for complex problems

Comparison Sorts

So far we have learnt the following sorting algorithms:

• InsertionSort
• SelectionSort
• MergeSort
• HeapSort
• QuickSort

All these algorithms proceed by comparing elements, hence the name comparison sorts. The best runtime we have achieved on such algorithms is in the worst case. In this section, we will prove that it’s impossible to do better.

A Very Brief Tast of Complexity Theory

Complexity theory deals with the difficulty of problems. Or more formally, it studies the limits to the efficiency of algorithms. The complexity theory often gives results like: every algorithm needs at least time in the worst case to solve problem . This kind of results stops us from wasting time trying to achieve the impossible, and informs the design of efficient algorithms.

A famous concept in the complexity theory is the NP-Completeness and NP-Complete Problem. This concept first arises from the study of Entscheidungsproblem (German for decision problem). An example of the decision problem is

Example

Does there exist an assignment of variables that satisfies a Boolean formula?

The NP-complete problems:

• contain >3000 important problems in different shapes.
• is easy to verify that a given solution means “yes”.
• no one knows how to find a solution in polynomial worst-case time.
• either no NP-complete problem is solvable in polynomial time, or all of them are.

To show that a given time is best possible, we need to find arguments that apply to all algorithms that can ever be invented.

Comparison Sorts as Decision Trees

From the previous sections we know that we can take the number of comparisons as lower time bound. w.l.o.g. we assume that elements are distinct, then we can assume that all comparisons have the form .

A decision tree reflects all comparisons a particular comparison sort makes, and how the outcome of one comparison determines future comparisons.

In the decision tree, a inner node means comparing and . The leaves are ordering established by the algorithm: A leaf contains a sorted output for a particular input. The execution of a sorting algorithm corresponds to tracing a simple path from the root down to a leaf.

An example of a decision tree:

Theorem

Every comparison sort requires comparisons in the worst case. The theorem can be also extended to an bound for the average-case time.

Proof. The worst-case number of comparisons equals the length of the longest simple path fomr the root to any reachable leaf, i.e. the height of the tree.

Every correct algorithm must be able to produce a sorted output for each of the possible orderings of the input. So the number of the leaves of the decision tree must be at least . Since a binary tree of height has no more than leaves, to accommodate we will need . Taking logarithms gets us .

So the worst-case number of comparisons is at least . Use the fact we get