Time Complexity
The number of machine instruction which a program executes during its runtime is called its time complexity. This number primarily depends upon the size of program's input that is approximately the number of strings to be sorted and their length and algorithm used.
"Sort an array of n strings by minimum search" is described by the expression c.n^2.
O Notation:
Runtime complexities are always specified in so called O-Notations.
The sorting method has a running time O(N^2). The expression O is called Landau's Symbol.
Mathematically speaking, O(N^2) stands for a set of functions.
f(n) <= c.n^2 The function n^2 is called an asymptotically upper bound of f. Generally the notation f(n) = O(g(n))
Evaluating run-time complexity
1 get a positive integer from input
2 if n > 10
3 print "This might take a while..."
4 for i = 1 to n
5 for j = 1 to i
6 print i * j
7 print "Done!"
Say that the actions carried out in step 1 are considered to consume time T1, step 2 uses time T2, and so forth. In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:
T1 + T2 + T3 + T7The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 ) times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T4( n + 1 ) time. The inner loop, on the other hand, is governed by the value of i, which iterates from 1 to n. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T6 time, and the inner loop test (step 5) consumes 2T5 time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T6 time, and the inner loop test (step 5) consumes 3T5 time.
Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression:
T6 + 2T6 + 3T6 + ... + (n-1)T6 + NT6
which can be factored as
T6[1+2+3+.....+(n-1) + n) = T6[1/2 (n^2 + n)]
The total time required to run the inner loop test can be evaluated similarly:
T5[1/2 (n^2 + 3n + 2)] - T5
Therefore the total running time for this algorithm is:
T1 + T2 + T3 + T7 + (n+1) T4 + T6[1/2 (n^2 + n)] + T5[1/2 (n^2 + 3n + 2)] - T5
As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n² is the highest-order term, so one can conclude that f(n) = O(n²).
Space ComplexityThe better the time complexity of an algo the faster the complexity will carry out in practice. Space complexity is the number of memory cells. A good algo tries to keep this number as small as possible.
Sorting Algos:
•Bubble Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1) auxiliary
•BiDirectional Bubble Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1) auxiliary
•Bucket Sort
Worst case performance: O(n2.k)
Best case performance: -
Average case performance: O(n.k)
Worst case space complexity: O(n.k)
•Comb Sort
Worst case performance: -
Best case performance: -
Average case performance: -
Worst case space complexity: O(1)
•Cycle Sort
Worst case performance: O(n2)
Best case performance: -
Average case performance: O(n2)
Worst case space complexity: O(1)
•Gnome Sort
Worst case performance: O(n2)
Best case performance: -
Average case performance: -
Worst case space complexity: O(1)
•Heap Sort
Worst case performance: O(n log n)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity: O(1)
•Insertion Sort
Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1)
•Merge Sort
Worst case performance: O(n log n)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity:
•Odd-Even Sort
•Pigeonhole Sort
Worst case performance: O(n+2k)
Best case performance: -
Average case performance: O(n+2k)
Worst case space complexity: O(2k)
•Quick Sort
Worst case performance: O(n2)
Best case performance: O(n log n)
Average case performance: O(n log n)
Worst case space complexity: O(log n)
•Quick Sort with Bubble Sort
•Selection Sort
Worst case performance: O(n2)
Best case performance: O(n2)
Average case performance: O(n2)
Worst case space complexity: O(1)
•Shell Sort
Worst case performance: -
Best case performance: n
Average case performance: O(n log2 n)
Worst case space complexity: O(1)
Reference:
Leda TutorilSort VisualizationAnalysis of Algorithms
