search
Log In
0 votes
26 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 solution is $\Theta(n\log \ n)$.

in Algorithms
edited by
26 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
24 views
Using the master method, you can show that the solution to the recurrence $T(n) = 4T(n/2) +n^2$ is $T(n) = \Theta(n^2)$.Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.
asked Apr 5, 2019 in Algorithms akash.dinkar12 24 views
0 votes
0 answers
2
20 views
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.
asked Apr 5, 2019 in Algorithms akash.dinkar12 20 views
0 votes
0 answers
3
0 votes
0 answers
4
...