1. Solve the recurrence relation using the iteration method T(n) = 4T()+ +n 2. Prove 4n3-2n...

Transcribed Image Text:

1. Solve the recurrence relation using the iteration method T(n) = 4T()+ +n 2. Prove 4n3-2n + 11 0(n) 3. Prove 3+50(4") using the definition of o 4. Consider the following algorithm Algo1(A, B) 1. count =0 2. for 1 to A 3. 4. for j = 1 to B count count+1 5. return count (a) what is the loop invariant property of the for loop given in line 2 (b) what is the loop invariant property of the for loop given in line 3 1. Solve the recurrence relation using the iteration method T(n) = 4T()+ +n 2. Prove 4n3-2n + 11 0(n) 3. Prove 3+50(4") using the definition of o 4. Consider the following algorithm Algo1(A, B) 1. count =0 2. for 1 to A 3. 4. for j = 1 to B count count+1 5. return count (a) what is the loop invariant property of the for loop given in line 2 (b) what is the loop invariant property of the for loop given in line 3