this is for holding javascript data
Alex Varghese edited p1.tex
about 10 years ago
Commit id: 0f7c411c026c5974797b114e66a44c1f62ef482a
deletions | additions
diff --git a/p1.tex b/p1.tex
index 1c6668d..66c1b44 100644
--- a/p1.tex
+++ b/p1.tex
...
\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 $2^j$ nodes. Each node will only have a problem of the size $n/2^j$ so at each node the time to complete it will be $(n/2^j)/log(n/2^j)$
Know this if we sum over all the log(n) levels we get:
$T(n) = \sum_{j=0}^{log(n-1)} 2^j[(n/2^j)/(log(n/2^j))]$
JESUS FUCKING CHRIST THIS PROBLEM IS LONG