Homework Problem #1
The homework is due before class 4/10/07. E-mail a copy of your analysis to nkuchta at cs with the subject '524P HW1'.
Analyze the complexity of the Odd/Even Interchange Sort (Parallel Bubble Sort):
Given array A[n], exchange odd and even indexed pairs if not ordered, then exchange even/odd pairs if not ordered, then repeat until sorted
Analyze with the CTA model (i.e. for P - number of processors, lambda - cost of communication between processors, d - degree of the tree if necessary), and charge the o/e-e/o pair c time if operands are local; ignore all other local computation