Question

Please help with this algorithms design problems. Thank you.

Use substitution method: 1. Show that the solution of T(n) = T(n-1) +n is O(n) Use master method to find tight asymptotic bounds: 2. T(n) = 2*T(n/4+n 3. T(n) = 2*T(n/4) + n2

Answer 1

1)  Using substitution method
T(n) = T(n-1) + n

T(n)
= T(n-1) + n
= T(n-2) + n-1 + n
= T(n-3) + n-2 + n-1 + n
= T(1) + 2 + ... + n-2 + n-1 + n
= 1 + 2 + ... + n-2 + n-1 + n
= n(n+1)/2
so, T(n) = O(n^2)

2)

T(n) = 2T (n/4)+n This is in the form of T(n) = a1 + f(n) so, we can use master's theorem. compare nogoo with f(n) a = 2, b=4 nlog, a = nlog,2 = n0.5 = Vn nloga = nlog 2 = n0.5 = n < f(n) = n so, this comes under case 3 so, time complexity is (f(n)) = e(n) Answer: e(n)


3)

T(n) = 2T(n/4)+n2 This is in the form of T(n)=aTC) + f(n) so, we can use master's theorem. compare nlogta with f(n) a = 2, b=4 nalog. a = nlog 2 = n0.5 = Vn nlog, a = nlog,2 = n0.5 = n < f(n) = n2 so, this comes under case 3 so, time complexity is (f(n)) = (nº) Answer: (n?)