Lab 6: Algorithm Analysis
Lab Structure
 Pick a partner.
 Help each other with the code as needed. Do not type for your partner
and avoid dictation, but
make sure your partner is able to finish the assignment.
 Make sure that your partner understands the mergesort enough to
take a test over it.
 Put your partner's name with yours in the header of the
sort.c file.
 If your partner is unable to complete the lab, your maximum grade is a 90%.
Runtime Complexity of Sorts
Analysis of Insertion Sort pp. 264266
 The insertion sort has nested for loops, each of which can take N iterations:
O(N^{2})
 If the list is already sorted, the inner for loop condition will fail everytime. Therefore,
if the list is sorted, the algorithm requires only N iterations.
 The number of times the inner loop executes is based on the number of inversions in
the list: an inversion is any two elements where the first element is larger than the second.
 The runtime of the insertion sort is O(I+N), where I is the number of inversions.
 A reverse sorted list has O(N^{2}) inversions.
 The insertion sort is O(N^{2}).
Analysis of the Mergesort pp. 276279
 The time to mergesort 1 element is 1: Time (1) = 1
 Time (N) = 2 Time (N/2) + N
 (Time (N))/N = (Time(N/2))/(N/2) + 1
 (Time (N/2))/(N/2) = (Time(N/4))/(N/4) + 1
 (Time (N/4))/(N/4) = (Time(N/8))/(N/8) + 1 . . .
 (Time (2))/(2) = (Time(1))/(1) + 1
 Now if we add up the equations, we get (Time (N))/N = (Time(N))/N = (Time(1))/1 + log N.
 Therefore the runtime is O(N log N).
Analysis of the Bubblesort
 Analyze the bubblesort.
 In a file called
bubblesort.txt , give the runtime complexity of the bubblesort
and why you believe it is the right complexity.
Turn in your code and a Makefile to create a.out .
Use sendlab.212.302 6 *.cpp *.h Makefile
