menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Cormen Edition 3 Exercise 4.3 Question 3 (Page No. 87)

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.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

0 votes
0 answers
1
24 views
Cormen Edition 3 Exercise 4.3 Question 8 (Page No. 87)
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.
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
Cormen Edition 3 Exercise 4.3 Question 7 (Page No. 87)
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.
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
20 views
Cormen Edition 3 Exercise 4.3 Question 6 (Page No. 87)
Show that the solution to $T(n) =T(\lfloor n/2 \rfloor+ 17) + n$ is $O(n\ log\ n)$
Show that the solution to $T(n) =T(\lfloor n/2 \rfloor+ 17) + n$ is $O(n\ log\ n)$
asked Apr 5, 2019 in Algorithms akash.dinkar12 20 views
0 votes
0 answers
4
21 views
Cormen Edition 3 Exercise 4.3 Question 2 (Page No. 87)
Show that the solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O$(lg$ $n)$.
Show that the solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O$(lg$ $n)$.
asked Apr 5, 2019 in Algorithms akash.dinkar12 21 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...