The program is required to implement insertion, bubble, quick and radix sort algorithms on a list of words in lexicographic order
According to the graph from our experimental result, the best case time complexity of bubble sort is obtained under the condition that all the elements in the array list are sorted in alphabetical order while the average case time complexity of bubble sort is obtained under the condition that all the elements in the array list are arranged randomly. Then, the worst case time complexity of bubble sort is obtained under the condition that all the elements in the array list are sorted in descending alphabetical order.
From the graph, the curve of the worst case and average case show quadratic growth. Hence, we can say that the time complexity of the worst case and average for bubble sort is O(n2). On the other hand, the curve of the best case grows linearly in the beginning of the graph. However, the curve grows in quadratic manner after a certain point due to the number of inputs exceeding the best case possibility. Therefore, we conclude that the time complexity of the best case for bubble sort is O(n2) too.
According to the graph, the first element has been selected as pivot in the quick sort. The best case time complexity of quick sort is obtained under the condition that all the elements in the array list are arranged randomly while the average case time complexity of quick sort is obtained under the condition that all the elements in the array list are sorted in alphabetical order. Then, the worst case time complexity of quick sort is obtained under the condition that all the elements in the array list are sorted in descending alphabetical order.
As we can see, the curve of the best case and average case grow in the way of log-linear in the graph. Hence, we can say that the time complexity of the best case and average case for quick sort is O(n*logn). On the other hand, the curve of the worst case shows quadratic growth in the graph. Therefore, we can conclude that the worst case time complexity for quick sort is O(n2).
According to the result obtained from the graph, the best case time complexity of insertion sort is obtained under the condition that all the elements in the array list are sorted in alphabetical order. The average case time complexity of insertion sort is obtained under the condition that all the elements in the array list are arranged in random order. Then, the worst case time complexity of insertion sort is obtained under the condition that all the elements in the array list are sorted in descending alphabetical order. After that, n - 1 number of comparisons will be performed for every nth element as each element will have to compare with each other.
As we can see, the curve of the worst case and average case shows quadratic growth in the graph. Hence, we can say that the time complexity of the worst case and average case for bubble sort is O(n2). On the other hand, the curve of the best case grows linearly in the graph. Therefore, we can conclude that the best case time complexity for bubble sort is O(n).
Based on the graph from our experiment, the best case time complexity of radix sort is obtained under the condition that all the elements in the array list are sorted in alphabetical order. The average case time complexity of radix sort is obtained under the condition that all the elements in the array list are arranged in random order. Then, the worst case time complexity of radix sort is obtained under the condition that all the elements in the array list are sorted in descending alphabetical order.
From the graph, the curves of three cases of radix sort exhibit the same pattern in the graph. As we can see from the graph, the curve for best case, worst case and average case grow linearly. Therefore, we can conclude that the best case, worst case and average case time complexity for radix sort is O(n + k).