Question

Problem 1 Use the master method to give tight asymptotic bounds for the following recurrences. a) T(n) = T(2n/3) +1 b) T(n) = 2T("/2) +n4 c) T(n) = T(71/10) +n d) T(n) = 57(n/2) + n2 e) T(n) = 7T(1/2) + 12 f) T(n) = 27(1/4) + Vn g) T(n) = T(n − 2) +n h) T(n) = 27T(n/3) + n° lgn

Answer 1

******************************************************************************************
Please Upvote the answer as it matters to me a lot :)
*****************************************************************************************
As per HomeworkLib expert answering guidelines,Experts are supposed to answer only certain number of questions/sub-parts in a post.Please raise the remaining as a new question as per HomeworkLib guidelines.
******************************************************************************************

a)
a=1 b=3/2 c= 0
using masters theorem
log_(3/2) 1 = 0 = c

T(n)= O(n^clogn)= O(logn)

b)

a=2 b=2 c= 4
using masters theorem
log₂ 2 = 2 < c(4)

T(n)= O(f(n))= O(n⁴)

c)

a=1 b=10/7 c= 1
using masters theorem
log_(10/7) 1 =0 < c (1)

T(n)= O(f(n))= O(n)

d)

a=5 b=2 c= 2
using masters theorem
log₂ 5 =2.321> c (2)

T(n)= O(n^{log_b a})= O(n^2.321)