Mazdak Farrokhzad edited Version3.tex  over 10 years ago

Commit id: 7994ac86daf2b0e2015e1288ac2a9f8c6a86f828

deletions | additions      

       

We define the function as:  $$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. $$   f_1(j,i) = \sum{k=i}^j d = d \sum{k=i}^j 1 = d(1 + j - i) = d + dj - di   $$