DERIVING TIME COMPLEXITY FUNCTIONS:

Linear search algorithm:

  *** WORST CASE

   index = -1                                       --
   i = 0                                             |
   while ((i < L.length) and (index == -1))      --  |
	if (L[i] == target)                -- --  |  |
	    index = i                      --  |  |  |
	i = i + 1                           | -- -- --
                                            2  |  |  |
                                               |  |  |
                                           2 + 1  |  |
                                           = 3    |  |
                                                  |  |
                                       n(3 + 1) + 1  |
				       = 4n + 1      |
                                                     |
                                          (4n + 1) + 2
                                          = 4n + 3

		=> T(n) = 4n + 3

  *** BEST CASE

   index = -1                                       --
   i = 0                                             |
   while ((i < L.length) and (index == -1))      --  |
	if (L[i] == target)                -- --  |  |
	    index = i                      --  |  |  |
	i = i + 1                           | -- -- --
                                            2  |  |  |
                                               |  |  |
                                           2 + 1  |  |
                                           = 3    |  |
                                                  |  |
                                       1(3 + 1) + 1  |
				       = 5           |
                                                     |
                                                 5 + 2
                                                 = 7

		=> T(n) = 7


Binary search algorithm:

  *** WORST CASE

   index = -1                                              --
   left = 0                                                 |
   right = L.length - 1                                     |
   while ((left <= right) and (index == -1))            --  |
	index = (left + right) / 2                   --  |  |
	if (target != L[index])                   --  |  |  |
	    if (target > L[index])          -- --  |  |  |  |
		left = index + 1             |  |  |  |  |  |
	    else                             |  |  |  |  |  |
		right = index - 1           --  |  |  |  |  |
	    index = -1                       | -- -- -- -- --
                                             2  |  |  |  |  |
						|  |  |  |  |
					    2 + 1  |  |  |  |
					    = 3    |  |  |  |
						   |  |  |  |
					       3 + 1  |  |  |
					       = 4    |  |  |
						      |  |  |
						  4 + 1  |  |
						  = 5    |  |
						         |  |
			                 (#)  k(5 + 1) + 1  |
					      = 6k + 1      |
                                                            |
                                                 (6k + 1) + 3
					         = 6k + 4
					     (#) = 6(log_2 n) + 4

		=> T(n) = 6(log_2 n) + 1

  *** BEST CASE

   index = -1                                        --
   left = 0                                           |
   right = L.length - 1                               |
   while ((left <= right) and (index == -1))      --  |
	index = (left + right) / 2             --  |  |
	if (target != L[index])             --  |  |  |
	    if (target > L[index])           |  |  |  |
		left = index + 1             |  |  |  |
	    else                             |  |  |  |
		right = index - 1            |  |  |  |
	    index = -1                      -- -- -- --
                                             |  |  |  |
					     |  |  |  |
					     1  |  |  |
					        |  |  |
					    1 + 1  |  |
					    = 2    |  |
						   |  |
			                1(2 + 1) + 1  |
					= 4           |
                                                      |
                                                  4 + 3
					          = 7

		=> T(n) = 7


(#) = This loop executes k times, where k is the number of times you can
       divide n by 2 until the result is less than 1. This implies:

		      2^k = n
		log_2 2^k = log_2 n
		        k = log_2 n