Register

Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)

612 views
0 votes
0 votes
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence

$T(n) = \begin{cases} 2 \text{,                        if n=2, }  \\2T(n/2)+n \text{,    if n=$2^k$,for k >1} \end{cases}$

is $T(n) = n\ lg\ n$.
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
akash.dinkar12 asked Jun 27, 2019
301 views
Cormen Edition 3 Exercise 7.2 Question 1 (Page No. 178)
Use the substitution method to prove that the recurrence $T(n)=T(n-1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
Use the substitution method to prove that the recurrence $T(n)=T(n-1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
User Avatar
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Apr 5, 2019
217 views
Cormen Edition 3 Exercise 4.6 Question 2 (Page No. 106)
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$.
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 a...
User Avatar
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Apr 5, 2019
213 views
Cormen Edition 3 Exercise 4.4 Question 2 (Page No. 92)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$.Use the substitution method to verify your answer
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$.Use the substitution method to verify your answer
User Avatar
Link Copied!