Lab 6: Algorithm Analysis

Lab Structure

1. Pick a partner.
2. 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.
3. Make sure that your partner understands the mergesort enough to take a test over it.
4. Put your partner's name with yours in the header of the sort.c file.
5. If your partner is unable to complete the lab, your maximum grade is a 90%.

Runtime Complexity of Sorts

Analysis of Insertion Sort pp. 264-266

• The insertion sort has nested for loops, each of which can take N iterations: O(N²)
• 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²) inversions.
• The insertion sort is O(N²).

Analysis of the Mergesort pp. 276-279

1. The time to mergesort 1 element is 1: Time (1) = 1
2. Time (N) = 2 Time (N/2) + N
3. (Time (N))/N = (Time(N/2))/(N/2) + 1
4. (Time (N/2))/(N/2) = (Time(N/4))/(N/4) + 1
5. (Time (N/4))/(N/4) = (Time(N/8))/(N/8) + 1 . . .
6. (Time (2))/(2) = (Time(1))/(1) + 1
7. Now if we add up the equations, we get (Time (N))/N = (Time(N))/N = (Time(1))/1 + log N.
8. 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.