Jeremy Ting edited p1.tex  about 10 years ago

Commit id: a8e077d7855e479e05d13a1f2cc2e4f46f106f5c

deletions | additions      

       

\item  $T(n) = 5T(\frac{n}{5})+ \frac{n}{lgn}$  So if we are to look at the recursion tree this relation creates we can observe that at the jth level there will be $5^j$ nodes. Each node will only have a problem of the size $n/5^j$ $\frac{n}{5^j}$  so at each node the time to complete it will be $(n/5^j)/log(n/5^j)$ Know this if we sum over all the log(n) levels we get: