[Cleptography]

Analyzing the efficiency of algorithms

1 1 1 1 1
e = --- + --- + --- + --- + --- + ...
0! 1! 2! 3! 4!

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:

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

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

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

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

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

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)