Show that the solution of  = T(\lceil n/2 \rceil) + 1) is O(lg n).
我们猜想  \le c\lg(n-2) )
 = T(\lceil n/2 \rceil) + 1 \le T(n/2+1) +1 \\ ~ \hspace{15 mm} \le c\lg(n/2-1)+1 \\ ~ \hspace{15 mm} =clg(n-2) -c\lg2 + 1 \\ ~ \hspace{15 mm} \le clg(n-2) )
We saw that the solution of  = 2T(\lfloor n/2 \rfloor) + n) is O(n lg n). Show that the solution of this recurrence is also Ω(n lg n). Conclude that the solution is Θ(n lg n).
我们假设 \ge cn\lg{n} )
 = 2T(\lfloor n/2 \rfloor) + n \\ ~ \hspace{15 mm} \ge cn(\lg{n} - \lg{2})+n \\ ~ \hspace{15 mm} =cn\lg{n} +(1-c\lg{2})n \\ ~ \hspace{15 mm} \ge cnlg(n) \\ ~ \hspace{15 mm} for ~ 1-c\lg{2} < 0 )
Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T (1) = 1 for the recurrence (4.4) without adjusting the boundary conditions for the inductive proof.
我们假设  \le n\lg{n}+n)
 \le 2(c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) + \lfloor n/2 \rfloor) + n \\ ~ \hspace{15 mm} \le 2c(n/2)\lg(n/2) + 2(n/2) + n \\ ~ \hspace{15 mm} \le cn\lg(n/2) + 2n \\ ~ \hspace{15 mm} \le cn\lg{n} - \lg{2}cn + 2n \\ ~ \hspace{15 mm} \le cn\lg{n} + (2-c)n \\ ~ \hspace{15 mm} \le cn\lg{n} + n ~~~~~~~~~~~~ for ~ c \ge 1 )
Show that Θ(n lg n) is the solution to the "exact" recurrence (4.2) for merge sort.
我们假设 \ge cn\lg{n} )
 \ge 2T(n/2) + kn \\ ~ \hspace{15 mm} =cn\lg{n} +(k-c\lg{2})n \\ ~ \hspace{15 mm} \ge cn\lg{n} ~~~~~~ if ~ k \le c\lg{2} )
我们假设 \le c(n-2)\lg(n-2) )
 \le T(n/2+1) + T(n/2) + kn \\ ~ \hspace{15 mm} \le c(n-2)\lg(\frac{n-2}{2}) + kn \\ ~ \hspace{15 mm} = c(n-2)\lg(n-2) +kn - c\lg{2}(n-2) \\ ~ \hspace{15 mm} \le c(n-2)\lg(n-2) ~~~~~~~~if~~kn \le c\lg{2}(n-2) )
Show that the solution to  = 2T(\lfloor n/2 \rfloor + 17) + n ) is O(n lg n).
我们假设 \le c(n-a)\lg(n-a) )
 \le 2c(\lfloor n/2 \rfloor + 17 - a)\lg(\lfloor n/2 \rfloor + 17-a) + n\\ ~ \hspace{15 mm} \le 2c(n/2 +1+ 17 - a)\lg( n/2 +1+ 17-a) + n \\ ~ \hspace{15 mm} \le c(n+36-2a)\lg(\frac{n+36-2a}{2})+n \\ ~ \hspace{15 mm} \le c(n+36-2a)\lg(n+36-2a) - c(n+36-2a)+n \\ ~ \hspace{15 mm} \le c(n+36-2a)\lg(n+36-2a) ~~~if ~~ c > 1 \\ ~ \hspace{15 mm} \le c(n-a)\lg(n-a) ~~~~if ~~ a \ge 36 )
Solve the recurrence  = 2T(\sqrt{n})+1 ) by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.
设n = lgn,得到新的递归式
 = 2T(2^{n/2}) + 1)
再令S(n) = T(2^n)可以得到
 = S2(m/2) + 1)
按照前面的方法解这个递归式即可
Follow @louis1992 on github to help finish this task.