Jeremy Ting edited p1.tex  about 10 years ago

Commit id: f385b43a441d78029b6fcad21e8f14c9d688c11b

deletions | additions      

       

$T(n) = \theta(\sqrt{n})$  \item  $T(n) = T(n-1) + lg(n)$  $T(n-1) = T(n-2) + lg(n-1)$  $T(n-2) = T(n-3) + lg(n-2)$  $T(1) = T(0) + lg(1)$  $T(n) + \sum_{i=1}^{n-1} T(i) = \sum_{i=1}^{n-1} T(i) since T(0) = T(1) + \sum_{i=1}^{n} lg(k)$  \end{enumerate}