1.  Recurrence relations

Running time of merge sort:

T(n) = 2T(ⁿ/₂)+n with T(1) = 0

Assume we want T(n) = O(n)

Then T(n) = 2O(ⁿ/₂)+n = O(n)? Wrong! Bad!

Instead, try: T(n) = cn then T(n) = 2cⁿ/₂+n = (c+1)n which doesn't work.

try: T(n) = cnlogn then T(n) = 2cⁿ/₂logⁿ/₂+n = cnlogⁿ/₂+n = cnlogn-cn+n which is solvable for c = 1 .

2.  All Prefix scan

The Random-Mate algorithm essentially has every node in the list guess it's parity. The algorithm (covered last meeting) works in 2 phases. In the first phase, nodes are eliminated while in the second phase, you back up the tree filling in the values of each node as in Wiley's algorithm.

2.1  Timing analyses

Probability that a node is removed from the list at each stage in the forward algorithm is ³/₄ . So P_t = (³/₄)^t = probability that a node is still in the list after t rounds. If we want P_t = [1/( n²)] then t = 2log_⁴/3n .

The probability that no node is left in the list is: P_left £ å_{i = 1}^n-1P_t £ nP_t £ ¹/_n if t = 2log_⁴/3n

2.2  Work analyses

Because of the random nature of this algorithm it is difficult to group enough nodes on each processor s.t. every processor will always have work to do. A prescan can be done over the elements to reallocate their location at each step.

3.  Another random list ranking algorithm

1. Make [(n)/( logn)] queues of size logn
2. Set the sex of all nodes to M.
3. Reset sex of top in each queue to a random sex.
4. If top element is F and points to M, the splice out F

The algorithm works on a doubly linked list.

3.1  Timing analyses

Timing is O(logn) with high probability

Let P(head) = ¹/₄ and P(tail) = ³/₄

Let S^p_t = #head in t trials.

P(S^p_t < logn) can be bounded by Chernoff Bounds

3.1.1 Chernoff Bound

P(S_t^p < (1-b)pt) < e^{-b2[(pt)/ 2]} for 0 £ b £ 1

In particular, P(S_16logn^1/₄ < (¹/₄)4logn) < e^{-[(32)/( 42)][(4logn)/ 2]} = e^-9/₈logn = [1/( n^9/₈)] < ¹/_n

= probability that a processor is not done.

The probability that all processors is done is £ å_{i = 1}^nlogn1/_n = [(n)/( logn)]¹/_n = [1/( logn)] .