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

function Recurse(A[1..n])
        f1(n)
        t1 <-- Recurse(A[1..(n-1)])
        t2 <-- Recurse(A[(2..n])
        return (t1+t2)
end function
**********************************
T(1) = O(1)
So, total run time,
T(n) = O(n) + T(n-1) + T(n-1) + O(1)
     = O(n) + 2T(n-1)
     = O(n) + 2[O(n-1)+2T(n-2)]
     = O(n) + 2O(n-1) + 4T(n-2)
     .......
     = O(n) + 2^1*O(n-1) + 2^2*O(n-2) + ...+ 2^(n-1)*T(1)
     = O(n) + 2^1*O(n) + 2^2*O(n) + ...+ 2^(n-1)*O(1)
     = O(n)*(1+ 2^1 + 2^2 + ...+ 2^(n-1))
     = O(n)* {(2^n)-1}/(2-1)
     = 2^n * O(n) - O(n)
     = 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)
        m <-- n/3
        t1 <-- Recurse(A[1..m])
        t2 <-- Recurse(A[(m+1)..2m])
        t3 <-- Recurse(A[(2m+1)..3m])
        return (t1+t2+t3)/3
end function
*********************************

T(1) = O(1)
So, total run time,
T(n) = O(logn) + O(1) + 3T(n/3)
     = O(logn) + 3T(n/3)
     = O(logn) + 3[O(log(n/3)) + 3T(n/9)]
     = O(logn) + 3O(logn) + (3^2)T(n/(3^2))
     ......
     = O(logn)*(1+3+3^2+...+3^i) + (3^i)*T(n/(3^i))
     = O(logn)((3^i)/2) + n*T(1) //assuming n/(3^i)=1
     = O(logn)(n/2) + nO(1)
     = O(nlogn) + O(n)
     = O(nlogn)