search
Log In
0 votes
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$.
in Algorithms 35 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
40 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.
asked Apr 5, 2019 in Algorithms akash.dinkar12 40 views
0 votes
1 answer
3
69 views
Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divide and conquer method, dividing each matrix into pieces of size $n/4 *n/4$,and the divide and combine ... is the largest integer value of $a$ for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm?
asked Apr 5, 2019 in Algorithms akash.dinkar12 69 views
0 votes
0 answers
4
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
...