Analyzing algorithms that include while loops -

when analyzing algorithms, don't have issues for loop while have problems analyzing running time of algorithms involves while loop. i'll show example express question.

the following 1 part of coin-change algorithm (well-known algorithm of us) studying right now:

counter = 0 s = 0 while(s <= n/100)    s = s+1    t1 = n- 100*s    h = 0      while(h <= t1/50)           h = h +1           t2 = t1 - 50*h  ... 

can explain best way of knowing running time of such algorithms have nested while loops?

the while loop way of writing loop assessing complexity should not different.

here, outer while loop runs n times in complexity world (proportional n in real world) since s increases 1 each iteration , runs until s reaches value proportional n.

the inner loop assume little confused about, runs t1 times (again in complexity world) t1 = n - 100s. thinking algorithm o(n^2) t1 decreases in each iteration inner loop runs fewer number of times each subsequent iteration , may not o(n^2).

t1 different each iteration entire set of iterations run for: n - 100 + n - 200 + n - 300 + .... 0 times. because numbers of terms in series proportional n, summation have n squared term , reporting complexity lower order terms ignored need not worry rest of numbers sum to. algorithm o(n^2).

the trick ignore constant , lower order terms @ each step , becomes easy !