Deriving upper bounds on the running time of selection sort


Assume as input a list L, L[1],...,L[n], of integers. Let T(n) be the running
time of the selection sort algorithm as a function of the input size n = the #
of integers in the given list L.


METHOD #1:

Work out from innermost nested control structure and multiply as you go.


    for i = 1 to n - 1 do                  __
	cur = i                         --  |
	for j = i + 1 to n do        --  |  |
	    if (L[j] < L[max]     --  |  |  |
	        cur = j        -- --  |  |  |
	temp = L[cur]           |  |  |  |  |
	L[i] = L[cur]           |  |  |  |  |
	L[cur] = temp           |  |  | -- --
                              = 1  |  |  |  |
                                   |  |  |  |
	                        <= 2  |  |  |
                                      |  |  |
                  <= (n - 1)(2 + 1) + 1  |  |
                   = 3n - 2              |  |
                                         |  |
                           <= (3n - 2) + 4  |
                            = 3n + 2        |
                                            |
                 <= (n - 1)((3n + 2) + 1) + 1
                  = 3n^2 + 3n - 3n - 3 + 1
                  = 3n^2 - 2

	Hence, T(n) <= 3n^2 - 2


METHOD #2

Sum # executions of individual statements

		                                      # Executions
                                         -----------------------------------
    for i = 1 to n - 1 do                n 

	cur = i                          n - 1

	for j = i + 1 to n do            ((n - 1) + 1) + ((n - 2) + 1) + ...
                                          (2 + 1) + (1 + 1)
                                          = n + (n - 1) + ... + 3 + 2
					  = SUM_{k = 2}^{n} k

	    if (L[j] < L[max]            (n - 1) + (n - 2) + ... + 2 + 1
					  = SUM_{k = 1}^{n - 1} k
                                          

	        cur = j                  <= (n - 1) + (n - 2) + ... + 2 + 1
					  = SUM_{k = 1}^{n - 1} k

	temp = L[cur]                    n - 1

	L[i] = L[cur]                    n - 1
 
	L[cur] = temp                    n - 1


	Hence,

		T(n) <= n + 4(n - 1) + SUM_{k = 2}^{n} k
			             + 2(SUM_{k = 1}^{n - 1} k)
                      = 5n - 4 + (SUM_{k = 1}^{n} k) - 1
			             + 2(1/2(n - 1)n)
                      = 5n - 5 + (1/2(n(n + 1)) + n^2 - n
                      = 5n - 5 + 1/2(n^2) + 1/2n + n^2 - n
                      = 3/3(n^2) + 9/2n - 5
	

Note that the bound derived in method #2 is tighter but is determined at the
expense of much more algebra.