DERIVING TIME COMPLEXITY FUNCTIONS:

Selection sort algorithm:

  *** WORST CASE

    for index = 1 to n - 1 do                       --
        min = index                              --  |
        for scan = index + 1 to n do          --  |  |
	    if (L[scan] < L[min])	   --  |  |  |
	        min = scan 		   -- --  |  |
        temp = L[min] 			    |  |  |  | 
        L[min] = L[index] 		    |  |  |  |
        L[index] = temp 		    |  | -- --
					    2  |  |  |
					       |  |  |
			      (n - 1)(2 + 2) + 2  |  |
		              = (4n - 4) + 2      |  |
		              = 4n - 2            |  |
					          |  |
                                       (4n - 2) + 4  |
				       = 4n + 2      |
						     |
			     (n - 1)((4n + 2) + 2) + 2
			     = (n - 1)(4n + 4) + 2
			     = (4n^2 + 4n - 4n - 4) + 2
                             = 4n^2 - 2 

		=> T(n) = 4n^2 - 2

  *** BEST CASE (given list is sorted)
  
    for index = 1 to n - 1 do                       --
        min = index                              --  |
        for scan = index + 1 to n do          --  |  |
	    if (L[scan] < L[min])	   --  |  |  |
	        min = scan 		   -- --  |  |
        temp = L[min] 			    |  |  |  | 
        L[min] = L[index] 		    |  |  |  |
        L[index] = temp 		    |  | -- --
					    1  |  |  |
					       |  |  |
			      (n - 1)(1 + 2) + 2  |  |
		              = (3n - 3) + 2      |  |
			      = 3n - 1	          |  |
                                        (3n - 1)+ 4  |
				        = 3n + 3     |
						     |
			       (n - 1)(3n + 3 + 2) + 2
			       = (n - 1)(3n + 5) + 2
			       = 3n^2 + 5n - 3n - 5 + 2
			       = 3n^2 + 2n - 3

		=> T(n) = 3n^2 + 2n - 3

Bubble sort algorithm:

  *** WORST CASE

        sorted = false                                        --
        while (!sorted)                                    --  |
            sorted = true                              --   |  |
            for i = 2 to n do                       --  |   |  |
                if (L[i - 1] > L[i])             --  |  |   |  |
                    swap = L[i - 1]           --  |  |  |   |  |
                    L[i - 1] = L[i]            |  |  |  |   |  |
                    L[i] = swap                |  |  |  |   |  |
                    sorted = false            -- -- -- --  -- --
                                               |  |  |  |   |  |
                                               4  |  |  |   |  |
                                                  |  |  |   |  |
                                                  5  |  |   |  |
                                                     |  |   |  |
                                    (n - 1)(5 + 2) + 2  |   |  |
                                    = 7n - 7 + 2        |   |  |
                                    = 7n - 5            |   |  |
                                             (7n - 5) + 1   |  |
                                             = 7n - 4       |  |
                                                            |  |
                                      n((7n - 4) + 1) + 1 (*)  |
                                      = n(7n - 3) + 1          |
                                      = 7n^2 - 3n + 1          |
                                      = 7n^2 - 3n + 1          |
                                                               |
                                               7n^2 - 3n + 1 + 1
                                               = 7n^2 - 3n + 2

(*) - Note that in the worst case, i.e., the given list is sorted in
       reverse of the requested order, the outer WHILE-loop executes
       (n - 1) times to move the element in the nth position to the
       first position and then one final time to verify that the
       list is sorted.

  *** BEST CASE (given list is sorted)

        sorted = false                                        --
        while (!sorted)                                    --  |
            sorted = true                              --   |  |
            for i = 2 to n do                       --  |   |  |
                if (L[i - 1] > L[i])             --  |  |   |  |
                    swap = L[i - 1]           --  |  |  |   |  |
                    L[i - 1] = L[i]            |  |  |  |   |  |
                    L[i] = swap                |  |  |  |   |  |
                    sorted = false            -- -- -- --  -- --
                                               |  |  |  |   |  |
                                               0  |  |  |   |  |
                                                  |  |  |   |  |
                                                  1  |  |   |  |
                                                     |  |   |  |
                                    (n - 1)(1 + 2) + 2  |   |  |
                                    = 3n - 3 + 2        |   |  |
                                    = 3n - 1            |   |  |
                                             (3n - 1) + 1   |  |
                                              = 3n          |  |
                                                            |  |
                                              (1)(3n + 1) + 1  |
                                              = 3n + 2         |
                                                               |
                                                      3n + 2 + 1
                                                      = 3n + 3
  
Insertion sort algorithm:

  *** WORST CASE

    for index = 2 to n do                                --
        key = L[index]                                --  |
        position = index                               |  |
        while ((position > 0) and                  --  |  |
	       (L[position - 1] > key))             |  |  |
	    L[position] = L[position - 1]       --  |  |  |
	    position = position - 1             -- --  |  |
        L[position] = key                        |  | -- --
					         2  |  |  |
                                                    |  |  |
			           (n - 1)(2 + 1) + 1  |  |
                                   = (3n - 3) + 1      |  |
				   = 3n - 2            |  |
                                                       |  |
                                            (3n - 2) + 3  |
					    = 3n + 1      |
                                                          |
                                  (n - 1)((3n + 1) + 2) + 2
				  = (n - 1)(3n + 3) + 2
                                  = (3n^2 + 3n - 3n - 3) + 2
                                  = 3n^2 - 1

		=> T(n) = 3n^2 - 1

  *** BEST CASE (given list is sorted)

    for index = 2 to n do                                --
        key = L[index]                                --  |
        position = index                               |  |
        while ((position > 0) and                  --  |  |
	       (L[position - 1] > key))             |  |  |
	    L[position] = L[position - 1]       --  |  |  |
	    position = position - 1             -- --  |  |
        L[position] = key                        |  | -- --
					     (#) 0  |  |  |
                                                    |  |  |
			                     1(0 + 1)  |  |
				             = 1       |  |
                                                       |  |
                                                   1 + 3  |
					           = 4    |
                                                          |
                                         (n - 1)(4 + 2) + 2
				         = (n - 1)(6) + 2
				         = (6n - 6) + 2
				         = 6n - 4

		=> T(n) = 6n - 4

(#) = Note that if list is sorted, the inner WHILE loop never
       executes.