Adversarial Arguments

Example 1

We can find the maximum element in an unsorted array in $O(n)$ time. How can we argue that this is optimal?

Idea: Show that any algorithm which executes a number of steps that is "too small" can be fooled by at least one input.

We show that with only $n-1$ steps, we cannot find the max in the array.

Adversary strategy:

1. When the algorithm asks for the number at position $i$ in $A$, we return 0.
2. We tell the algo: now that you executed your $n-1$ steps, go ahead if you're so smart: tell us what is the max?

So we cannot solve this in at most $n-1$ steps, we need $(n-1) + 1$ steps. Therefore $O(n)$ is optimal.

Example 2

We can find the median in an array in O(n) time using the selection algorithm. Can we do better?

We will prove that with at most $n-1$ steps no algo can compute the median.

Adversary strategy:

1. When the algo asks for the number at position $i$ in $A$, we return $A[i] = i$.
2. Algo says $A[k]$ is median, but we say that missing value is such a value that $A[k]$ is different

So it takes $\Omega ((n-1) + 1) steps to compute the median.

Decision Trees

The Sorting Problem

A decision tree is a binary tree $T$ defined as follows:

• $T$ has a finite number of nodes
• the label of each internal node of $T$ is of the form $A[i] : A[j]$
• from each internal node of $T$, there are two outgoing edges:
  • the label of the left outgoing edge is $\leq$
  • the label of the right outgoing edge is $>$

To each decision tree $T$ corresponds an algorithm $A_T$. Conversely, to each algorithm $A$ which uses only comparisons ($<, \leq, =, >, \geq$) corresponds a decision tree $T_A$.

Theorem

In the decision tree model, sorting an array of $n$ numbers takes $\Omega(n \log n)$ time.

Find an Element in a Sorted Array

In the decision tree mode, finding the position of an element $x$ in a sorted array $A[1..n]$ (or detecting that $x$ is not in $A$) takes $\Omega (\log n)$ time.

Merging Two Sorted Arrays

Let $A[1..n]$ and $B[1..n]$ be two sorted arrays. We know how to merge $A$ and $B$ into one single sorted array in $O(n)$ time.