DERIVING TIME COMPLEXITY FUNCTIONS:

Linear search algorithm:

  *** WORST CASE

   index = -1;                                      --
   i = 0;                                            |
   while ((i < L.length) && (index == -1))       --  |
	if (L[i] == target)                -- --  |  |
	    index = i;                     --  |  |  |
	i++;                                | -- -- --
                                            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) && (index == -1))       --  |
	if (L[i] == target)                -- --  |  |
	    index = i;                     --  |  |  |
	i++;                                | -- -- --
                                            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) && (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) + 1
					         = 6k + 1
					     (#) = 6(log_2 n) + 1

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

  *** BEST CASE

   index = -1;                                       --
   left = 0;                                          |
   right = L.length - 1;                              |
   while ((left <= right) && (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