Mazdak Farrokhzad edited Version1.tex  over 10 years ago

Commit id: c3b2a2ad6a087d1c81fa1cb0b03254dcca43a704

deletions | additions      

       

$$f_1(j,i) = \sum_{k=i}^j d = d \sum_{k=i}^j 1 = d(1 + j - i) = d + dj - di$$  $\displaystyle_f_2(n,i) $$f_2(n,i)  = \sum_{j=i}^{n-1} (c + f_1(j,i)) = \\ =$$   $$=  c\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} j - di\sum_{j=i}^{n-1} 1 = \\   = =$$   $$=  (c + d)\sum_{j=i}^{n-1} 1 + d(\frac{n(n-1)}{2} - \frac{i(i-1)}{2}) - di(n-i) = \\   = =$$   $$=  (c + d)\sum_{j=i}^{n-1} 1 + \frac{d}{2}n(n-1) + \frac{d}{2}i^2 + \frac{d}{2}(1-2n)i$ \frac{d}{2}(1-2n)i$$  $$  T(n) = a + f_3(n) = a + \sum_{i=0}^{n-1} (b + f_2(n,i)) = a + b\sum_{i=0}^{n-1} 1 + \sum_{i=0}^{n-1} f_2(n,i)