Efficiency is related to the running time of an algorithm
and thus is a way of measuring the algorithm’s performance. When comparing two algorithms that accomplish
the same task, you want to choose the more efficient one (the one with the
fastest running time). Running time is
normally related to the size of the problem, n. For example, n could be the
number of elements in a list.
An algorithm’s complexity is represented using big-oh
notation and the size of the problem. Big-oh
is an upper bound on the algorithm’s running time function (for large input
values). For example, constant running time
is represented by O(1). Linear running
time is represented by O(n). Big-oh
notation only uses the largest power of n and ignores lower powers and constants. For example, if f(n) = 4n^2 + 2 and g(n) = 26n^2 + 12n + 9999 are running
time functions, both are O(n^2).
Sorting is the process of ordering a collection of elements
in some way. For example, ordering the
list [8, 4, 63, 99, 7] to [4, 7, 8, 63, 99].
There are many different sorting algorithms, but they do not all have
the same efficiency. Their efficiency
depends on n, the length of the list, and the arrangement of the elements.
Efficiency of some sorting algorithms (links are to
animations of the algorithms):
Selection Sort:
O(n^2) in all cases
Insertion Sort:
worst (and average) case O(n^2)
best case O(n) # already sorted
Bubble Sort:
worst (and average) case O(n^2)
best case O(n) # already sorted
Merge Sort:
O(nlog(n)) in all cases
Quick Sort:
worst case O(n^2) # already sorted
best (and average) case
O(nlog(n))
Tim Sort:
worst (and average) case O(nlog(n))
best case O(n)
I like the idea of big-oh notation. I think it is a very useful way of
determining which algorithms are faster independent of factors like hardware or
other external effects. I think it also
helps with algorithm design. When
solving a problem, you need to think carefully about how you approach the problem
because there is a “best solution”, the most efficient one. For example, there are many different sorting
algorithms, and each is better than another in certain circumstances (length of
the list, if it is already sorted, if it is reverse sorted, etc.). Tim sort uses this idea. Tim sort is a hybrid sort (uses merge sort
and insertion sort) and it searches for already sorted sub lists. So, it is one of the best sorting algorithms
(at least compared to the ones I have been presented with so far).
Note: All animations and
pictures are from Wikipedia. I did not
create them.
