Analyzing the efficiency of algorithms 1 1 1 1 1 e = --- + --- + --- + --- + --- + ... 0! 1! 2! 3! 4! Code: public static void e1(int n) { double sum = 0.0; for (int i = 0; i < n; i++) { sum = sum + 1.0 / factorial(i); } System.out.println("e is approximately " + sum); } public static int factorial(int k) { int product = 1; for (int i = 1; i <= k; i++) { product = product * i; } return product; } Calculate total # of multiplications performed by e1(n): factorial requires k multiplications e1(n) requires 0 + 1 + 2 + ... + n-1 multiplications = ??? +--+--+--+--+ | |xx|xx|xx| +--+--+--+--+ | | |xx|xx| +--+--+--+--+ n units | | | |xx| +--+--+--+--+ | | | | | +--+--+--+--+ n units number of blank squares = 1 + 2 + ... + n-1 + n + number of xx squares = 1 + 2 + ... + n-1 ----------------------------------------------------- = total number of squares = 2*(1 + 2 + ... + n-1) + n = n^2 1 + 2 + ... + n-1 = (n^2 - n)/2 = 1/2 n^2 - 1/2 n So e1(n) requires 1/2 n^2 - 1/2 n multiplications in all Add count variable to e1 to see if theory agrees with practice "In theory there is no difference between theory and practice. In practice there is." --Yogi Berra n # muls = 1/2 n^2 - 1/2 n ---------------------------------- 0 0 1 0 2 1 3 3 4 6 5 10 6 15 7 21 8 28 9 36 10 45 We could use other measures of running time, such as # of comparisons, # of additions, or total # of arithmetic operations: factorial(k): # loop cycles = k # multiplications = k # comparisons = k+1 # additions = k # arithmetic operations = 2k e1(n): # loop cycles = n # multiplications = 1/2 n^2 - 1/2 n # comparisons = n+1 + [(0+1)+(1+1)+(2+1)+...+(n-1)+1] = 1/2 n^2 + 3/2 n + 1 # additions = [0+1+2+...+(n-1)] + 2n = 1/2 n^2 + 3/2 n # arithmetic operations = #muls + #adds + #divs = 1/2 n^2 - 1/2 n + 1/2 n^2 + 3/2 n + n = n^2 + 2n Whichever measure we use, we still end up with an n^2 term. We say that the running time of e1 is "order n squared" or O(n^2) Now consider an alternative way of computing e: Code: public static void e2(int n) { double sum = 0.0; double denom = 1.0; for (int i = 1; i <= n; i++) { sum = sum + 1.0 / denom; denom = denom * i; } System.out.println("e is approximately " + sum); } # loop cycles = n # multiplications = n # comparisons = n+1 # additions = 2n # arithmetic operations = #muls + #adds + #divs = n + 2n + n = 4n We say that the running time of e2(n) is "order n" or O(n) Examples O(1) = "constant time" 1, 6, 342, 5 trillion O(n) = "linear time" n, 3n+1, 40n + 5 trillion O(n^2) = "quadratic time" n^2, 1/100 n^2, 7n^2+3n+24 O(n^3) = "cubic time" O(n^3): 100n^3+700n^2+1000 O(log n) = "logarithmic time" binary search, fast exponentiation O(2^n) = "exponential time" lookahead in a game (show binary game tree) ==================================================================== FAST EXPONENTIATION Code: public static double fastpower(double base, int n) { if (n == 1) { return base; } else if (even(n)) { return squared(fastpower(base, n / 2)); } else { return base * fastpower(base, n - 1); } } Best case example: n=32 32 16 8 4 2 1 5 multiplications log2(n) multiplications in the best case Worst case example: n=31 31 30 15 14 7 6 3 2 1 8 multiplications about 2 log2(n) multiplications in the worst case (2 floor[log2(n)] exactly) O(log n) time ==================================================================== PRIME TESTING - How to determine if n is prime? Check all numbers 2, 3, 4, ..., n-1 to see if they divide n evenly Code: public static boolean primeTest1(int n) { if (n < 2) return false; for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } Worst case (when n is prime): n - 2 loop cycles 1 + n - 1 + n - 2 = 2n - 2 total comparisons O(n) time ----------------------------------------------------------------------- But no factors beyond n/2 exist, so we only need to check up to n/2 Example: 24 2 * 12 3 * 8 4 * 6 6 * 4 8 * 3 12 * 2 Code: public static boolean primeTest2(int n) { if (n < 2) return false; for (int i = 2; i <= n / 2; i++) { if (n % i == 0) return false; } return true; } Worst case: n/2 - 1 loop cycles 1 + n/2 + n/2 - 1 = n total comparisons = O(n) time ----------------------------------------------------------------------- But we only need to check up to sqrt(n) because of symmetry Example: 36 Example: 49 2 * 18 7 * 7 3 * 12 4 * 9 6 * 6 9 * 4 redundant 12 * 3 redundant 18 * 2 redundant Code: public static boolean primeTest3(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } Worst case: sqrt(n) - 1 loop cycles 1 + sqrt(n) + sqrt(n) - 1 = 2 sqrt(n) total comparisons O(sqrt n) time ----------------------------------------------------------------------- But we don't need to check even numbers beyond 2 Code: public static boolean primeTest4(int n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; } Worst case: (sqrt(n)-1)/2 = 1/2 sqrt(n) - 1/2 loop cycles 3 + (sqrt(n)-1)/2 + 1 + (sqrt(n)-1)/2 = sqrt(n) + 3 total comparisons O(sqrt n) time Loop cycles Comparisons Running time primeTest1 n - 2 2n - 2 O(n) primeTest2 n/2 - 1 n O(n) primeTest3 sqrt(n) - 1 2 sqrt(n) O(sqrt n) primeTest4 1/2 sqrt(n) - 1/2 sqrt(n) + 3 O(sqrt n)