Corrected Version

********Problem 1****************
Assume f1(n) = O(n). Find running time of the following recursive function

function Recurse(A[1..n])
        f1(n)				// O(n)
        t1 <-- Recurse(A[1..(n-1)])	// T(n-1)
        t2 <-- Recurse(A[(2..n])	// T(n-1)
        return (t1+t2)			// O(1)
end function

Total Runtime:
 T(n) = O(n) + 2*T(n-1) + O(1)  = 2*T(n-1) + O(n)
  				= 4*T(n-2) + 2*O(n) + O(n)
 				= 8*T(n-3) + 4*O(n) + 2*O(n) + O(n)
				.................
				.................
				= (2^k)*T(n-k) + O(n)(1+2+4+8+...+2^(k-1))  [   n-k=1
										k=n-1   ]
				= 2^(n-1)*T(1) + O(n)*((2^(n-1)-1)/(2-1))
				= O(n*(2^(n-1)-1))
				= O(n*2^n)
**********************************


***************Problem 2**********
Assume f1(n) = O(log n). Find running time of the following recursive function

function Recurse(A[1..n])
        f1(n)				// O(log n)
        m <-- n/3			// O(1)
        t1 <-- Recurse(A[1..m])		// T(n/3)
        t2 <-- Recurse(A[(m+1)..2m])	// T(n/3)
        t3 <-- Recurse(A[(2m+1)..3m])	// T(n/3)
        return (t1+t2+t3)/3		// O(1)
end function

Total Runtime:
 T(n) = 3*T(n/3) + O(log n) + O(1) + O(1)
      = 3*T(n/3) + O(log n)
      = 3*[3*T(n/3^2) + O(log(n/3))] + O(log n)
      = (3^2)*T(n/3^2) + 3*O(log n) + O(log n)
      .............................
      .............................
      = (3^k)*T(n/3^k) + (1 + 3 + 3^2 +.....+ 3^(k-1))*O(log n)
      = 3^(log3 (n)) + ((3^(log3 (n))-1)/(3-1))*O(log3 (n))  [  n/3^k = 1
					       		=> n = 3^k
					       		=> k = log3(n) ]
      = n + n*O(log3 (n))
      = O(n*log (n))

*********************************