retagged by
131 views
0 votes
0 votes
Using the master method, you can show that the solution to the recurrence $T(n) = 4T(n/3) +n$ is $T(n) = O(n^{log_34})$.Show that a substitution proof with the assumption $T(n) \leq cn^{log_34}$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.
retagged by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 5, 2019
170 views
We saw that the solution of $T(n) = T(\lceil n/2 \rceil) + n$ is $O(lg\ n)$. Show that the solution of this recurrence is also $\Omega(n\ lg\ n)$. Conclude that the solut...
0 votes
0 votes
0 answers
4