Jeremy Ting edited p1.tex  about 10 years ago

Commit id: b67ba2a596e891a1e55658e4288f52b24217d244

deletions | additions      

       

$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 $\frac{n}{5^j}$ so at each node the time to complete it will be $\frac{(\frac{n}{5^j})}{log(\frac{n}{5^j})}$   Know this if we sum over all the log(n) $log(n)$  levels we get: $T(n) = \sum_{j=0}^{log(n-1)} 5^{j}\frac{\frac{n}{5^j}}{log(\frac{n}{5^j})}$