Mazdak Farrokhzad edited Version3.tex  over 10 years ago

Commit id: 52f77934aab103ed5306516d86be2db1049a2980

deletions | additions      

       

$$T(n) = a + \sum_{i=0}^{n-1} f_3(n) = a + \sum_{i=0}^{n-1} (b + \sum_{j=i}^{n-1} (c + \sum_{k=i}^{j} d))$$  Each loop in the method corresponds to one sum or one method $f_i$ where the lowest index is the innermost sum/loop.  We define the other functions:     $$f_1(j,i) = \sum_{k=i}^j d = d \sum_{k=i}^j 1 = d(1 + j - i) = d + dj - di$$  $$  f_1(j,i) f_2(n,i)  = \sum_{k=i}^j d \sum_{j=i}^{n-1} (c + f_1(j,i))  = d \sum_{k=i}^j c\sum_{j=i}^{n-1}  1= d(1  + j - i) = d d\sum_{j=i}^{n-1} 1  + dj d\sum_{j=i}^{n-1} j  - di di\sum_{j=i}^{n-1} 1  $$