Efficiency Analysis

Can express run time as a recurrence relation: T(a,0) = 1, tex2html_wrap_inline166 if b>0.

Recall that we are interested in computing the worst-case running time for this process. (Why?)

Some of the obvious candidates for this don't work out. For example, how big is tex2html_wrap_inline162 compared to b? Neither of these hold for all a and b:

eqnarray28


next up previous
Next: Classic Sequence Up: EUCLID'S ALGORITHM Previous: Euclid's Algorithm