edited by
660 views
0 votes
0 votes

Use the master method to give tight asymptotic bounds for the following recurrences.

  1. $T(n)=2T(n/4) + 1$
  2. $T(n)=2T(n/4) +\sqrt{n}$
  3. $T(n)=2T(n/4) +n$
  4. $T(n)=2T(n/4) +n^2$
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
2
akash.dinkar12 asked Apr 5, 2019
276 views
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 5, 2019
245 views
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.