Bounding Recurrences Provide tight asymptotic upper and lower bounds for the fol

Question

Bounding Recurrences

Provide tight asymptotic upper and lower bounds for the following recurrences (i.e. (·)). You will be graded on your best 5 solutions out the 6. If you cannot give matching upper and lower bounds, give the best upper and lower bounds that you know how to. Correct answers without explanation are given full credit, but you may want to give a very brief justification for each problem, both for practice and for possible partial credit. (a) T(n) = 2T(n/2) + n 4

(b) T(n) = 16T(n/4) + n 2

(c) T(n) = 2T(n/3) + T(n/4) + n

(d) T(n) = T(n 1) + n

(e) T(n) = 3T(n/2) + 5n

(f) T(n) = T( n) + 7

Explanation / Answer

Answer :

a) T(n) = 2T(n/2) + n^4

Applying Master's Theorm, we have

a = 2 , b = 2 , c = 4, loga base b = log 2 base 2 = 1

Here c< loga base b , hence T(n) = O(n^c) = O(n^4)

b) T(n) = 16T(n/4) + n^2

Applying Master's Theorm , we have

a = 16 , b = 4 , c = 2

logabase b = log16 base 4 = 2

Here C = loga base b , therefore T(n) = theta(n^clog^k+1n) = theta (n^2logn)

c) T(n) = 2T(n/3) + T(n/4) + n

T(n) = O(n)

As both the divisions n/3 and n/4 end up till n times

d) T(n) = T(n- 1) + n^1/2

Applying backsubstitution method

T(n-1) = T(n-2) + (n-1)^1/2

=> T(n) = T(n-2) + (n-1)^1/2 + n^1/2

T(n-2) = T(n-3) +(n-2)^1/2 + (n-1)^1/2

=> T(n) = T(n-3) + (n-2)^1/2 + (n - 1) ^1/2 + n^1/2

.

.

T(n) = T(n - k) + ( n-k-1)^1/2 + (n-k-2)^1/2 ... + k^1/2

Let n = k

T(n) = T(0) + 1^1/2 + 2^1/2 + ... + n^1/2

= O(n^1/2)

DEAR STUDENT! DUE TO COMPANY NORMS WE ARE SUPPOSED TO ANSWER ONLY FOUR PARTS OF THE QUESTION CONTAINING MORE THAN 4 SUB PARTS. KINDLY POST SEPARATELY TO GET ANSWERED. HOPE THIS HELPS. THANKS

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.