You write a function that operates on an arbitrarily large volume of input.
Assuming that there is no bug - that it returns the right values every time (especially no infinite loops) - the only question now remains: how long does it take for the thing to finish?
Time is not an adequate means of measuring that because i could be running it on a better computer than you.
There are 3 ways of expressing time complexity, best case, worst case, and average case, and its performance depends on how "pre-sorted" the input already is and on the property of the algorithm itself.
Let us illustrate that with some sorting algorithms.
selection sort:
The selection sort iterates through every single element starting from the first index of the unsorted section, selecting the minimum, and places it to the front of the queue. Whatever input n is given, it takes n^2 steps to solve it. Therefore, the selection sort, worst case = best case = average case, running time can be expressed as: O(n^2)
quick sort:
the quick sort picks a pivot point and arranges two values at a time into the right order. The time complexity depends largely on how sorted the input already is. Therefore, worst case is O(n^2) if the input is a mess and it operates much like the selection sort. The best case is O(n log n) if the input is already sorted. The average case of the two is simply O(n) by simple algebra.
merge sort:
The merge sort takes a list of values and divide them into single elements, then compared each element with the adjacent list to merge into lists. The same process is repeated regardless of input, therefore, worst case = best case = average case, O(nlogn).
count sort
the count sort algorithm is usually used when the number of elements approximately equals to the number of possible key values.
There is only one case or runtime for count sort, and that is dependent on the size of input n and the number of key elements N
O(N + n)
I’m afraid that I have to debate with you Jack. You are correct to assert that selection sort has the same time complexities for best, average and worst case. However, I argue that selection sort at worst case is less efficient because it makes more switches than average and best case, even though the number of iterations remain the same. In other words, I believe that time complexity does not tell you everything about an algorithm’s efficiency. Additionally, you assert ‘by simple algebra’ that quick sort has an efficiency of O(n) for the average case. I argue that quick sort has an average-case complexity of O(n log n) because the number of comparisons is tightly bounded by n and the number of partitions is tightly bounded by log n. What are your thoughts?
ReplyDelete