search
Log In
0 votes
41 views
Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $c<1$,which is part of case 3 of the master theorem. Give an example of constants $a\geq 1$ and $b>1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
in Algorithms
edited by
41 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
43 views
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b)\geq cf(n)$ for some constant $c<1$ implies that there exists a constant $\epsilon >0$ such that $f(n)=\Omega(n^{log_ba+\epsilon})$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
2
35 views
Show that if $f(n)=\Theta(n^{log_ba}\lg^kn )$, where $k\geq0$ then the master recurrence has solution $T(n) =\Theta(n^{log_ba} \lg^{k+1}n)$.For simplicity, confine your analysis to exact powers of $b$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 35 views
0 votes
0 answers
3
39 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.
asked Apr 5, 2019 in Algorithms akash.dinkar12 39 views
0 votes
0 answers
4
30 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)$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 30 views
...