Modifying the condition in second loop. Changing from j<=i to j<i. Reason: Asymptotically it wont make a difference.
Total T(n) : OuterLoop * Middle * Innermost
Outer loop Executes: logn times
Innermost Executes: n times
Aggregate Analysis of Middle loop :
Lets examine the middle one. Since it is not trivial to identify. Lets take an example.
Assume n=8
When i =1 j will execute for 1 time ( iterNo = 0 )
When i =2 j will execute for 2 time ( iterNo = 0,1 )
When i =4 j will execute for 4 time ( iterNo = 0,1,2,3 )
When i =8 j will execute for 8 time ( iterNo = 0,1,2,3,5,4,6,7 )
Thus middle loop is executing sum of GP with last term = n.
Height of this GP will be 2^h = n
Hence h = log n
Thus Sum of GP = ( 2^(logn + 1) - 1)/ ( 2 -1 )
Simplifying gives n
Hence total T(n) = n * n
= n^2