Analysis of Algorithms

Compare different programs for resources used ( N : input size )

• Memory : s(N)

• computing time : T(N)

• Plotter distace

• Average case (typical case)  <--->   Worst case

• space/time tradeoff

Example : gcd

• Brute--force :   s = 3

              T(u,v) = min(u,v)- gcd(u,v)+1

• Euclid's  algorithm :

           ˙ (overhead for recursive call ) * ( # recursive calls )

                     language featuers

           ˙  complicate

"  90%  CPU Time on 10% Code "  !!!

• leads to better understanding of the program

• leads to improvements to the program