# ADA (a) If f(n) = O(nlogba-e ),

ADA Homework 1Priya Rajpurohit2015073Group members: Alka 2016010 Shika 2012094Problem-1: Solve the recurrences 10 points Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n ? 2.{The Master method is a general method for solving (getting a closed form solution to) recurrence relations that arise frequently in divide and conquer algorithms, which have the following form: T(n) = aT(n/b) + f(n) where a ? 1, b > 1 are constants, and f(n) is function of non-negative integer n. There are three cases. (a) If f(n) = O(nlogba-e ), for some e> 0, then T(n) = ?(nlogba ). (b) If f(n) = ?(nlogba ), then T(n) = ?(nlogba log n). (c) If f(n) = ?(nlogba+e ) for some e> 0, and af(n/b) ? cf(n), for some c < 1 and for all n greater than some value n> 0 , Then T(n) = ?(f(n)).}(a) T(n) = 4T(n/5) + 5nSol. By Master’s Theorem,case 3 a=4,b=5,c<1 f(n)=(nlog54) Regularity condition: 4n <= (0.9)(5n) T(n)=(n) (b) T(n) = 5T(n/4) + 4nSol. By Master's Theorem, case1 a=5,b=4 f(n)=O(nlog45) T(n)=O(nlog45) (c) T(n) = 4T( ?n ) + log5nSoln. By Substitution, T(n) =42T(n1/22) +12log5n+log5n . . T(n)=4kT(n1/2k) +(12k-1+....+12)log5n+log5n n1/2k=2(T(1)=2) k=log log n T(n)=4loglognT(n1/2loglogn) +(12loglogn-1+....+12)log5n+log5n T(n)= log2n+2log5n-2log5nn T(n) =O(log2n) (d) T(n) = 2T(n/3) + 1 (solve using substitution method only) Sol. By substitution, T(n)=2(2T(n/9)+1)+1 T(n)=4T(n/9)+2+1 . . T(n)=2kT(n/3k)+2k-1 +…..+2+1 n/3k=1 k=log3n T(n)=2log3nT(1)+2log3n-1 +…..+2+1 T(n)=O(nlog32) (e) T(n) = 2T(n-1) + n ( For this n>1 T(1)=1 ) Sol. By substitution, T(n)=2(2T(n-2)+n-1)+1 T(n)=4T(n-2)+2n-1 … T(n)=2kT(n-k)+i=0k-12i(n-i)n-k=1k=n-1T(n)=2n-1T(1)+i=0n-22i(n-i)T(n)=O(2n)Problem-2: 5 pointsSuppose you are given an array A that contains n integers each of which are either 0 or 1. Furthermore, it is known that there is some index i such that A1 = A2 = … = Ai = 0 and Ai + 1 = Ai + 1 = … = An = 1. Design an algorithm that takes as input such an array and output this index at which the transition from 0 to 1 happens. For example, if the array is A = 0, 0, 0, 0, 1, 1, then your algorithm should output 5. Give pseudocode and analyse the running time of your algorithm.Sol. PSEUDOCODE: trans1(A,p,q): middle=int(p+q)/2 If (Amiddle == 0): If (Amiddle+1 == 1): Return middle+1 Else return trans1(A,middle+1,q) Return trans1(A,p,middle Since this algorithm is almost similar to binary search.Hence, T(n)O(log n).Problem-3: 5 points You are given a sorted array A with n integers and an integer w and you want to determine whether there exists two distinct indices i, j in the array such that Ai + Aj = w. Design a recursive algorithm for this problem. Write pseudocode and discuss running time. You should also argue the correctness of your recursive algorithm.Sol. PSEUDOCODE exist(A,w,p,q): if(q<=p): Return -1 if(Ap+Aq == w): Return 1 if(Ap+Aq