Lecture 3 - Notes

January 11, 2016

Weighted Quick Union --- Continued

Union

Proposition, The depth of any node is $\le \lg N$.

Proof:

The depth goes up (by 1) only on a union with $x$ where $x$ is in the smaller tree,

the size of the tree containing $x$ is at least twice as large on such a union
the size of a tree can double at most $\lg N$ times

Using rank instead of node count to track the size of the trees can reduce the space complexity since the maximum bit length for the rank is $\le \lg(\lg(N))$

Compression

We make nodes along the find path point to the root.

To do this with two passes we can perform a second loop setting every node to the root.

To do this with one path this make every other node in the path point to it's grandparent.

public int find(int i)
{
   while (i != id[i])
   {
      id[i] = id[id[i]]; //<-- Set the Grandparent
      i = id[i]; 
   }
   return i;
}

Comparison Based Sorting

In Comparison Based Sorting like,

Mergesort
Quicksort
Heapsort

Let's say we are sorting something sort([a,b,c]),

Example Sorting Tree

This comparison tree has 6 leaves. In general it has to be $\ge N!$ (because that's how many possible combinations there are).

The height is the worst case number of comparisons, in this case 3. What is the minimum height $h$ of an extended binary tree with $n$ leaves?

$\begin{align} n &\le 2^h \newline \lceil \lg n \rceil &\le h \end{align}$

Therefore the height for sorting is $\ge \lceil \lg{N!} \rceil$. We can bound $N!$ with,

$\begin{align} \left( \frac{n}{2} \right) ^ \frac{n}{2} \le N! \le N^N \end{align}$

and by taking the log,

$\begin{align} \frac{n}{2} \lg \left( \frac{n}{2} \right) \le \lg{N!} \le N \lg {N} \end{align}$

So comparison based sorting requires $\Omega (N \lg N)$ comparisons.