Recursion
Defined in terms of “itself”
Requires a stopping condition
Incorporates a simplifying step
Convergence

Program Running Times
What determines how fast a program will run?
Hardware
Compiler
Operating System
    Benchmarks
Program Running Times (cont.)
What determines how fast an algorithm will run?
Same things
How can we compare algorithms objectively?
Use Problem Size as a determining factor
Compare Growth Rate as a function of input size
Program Running Times (cont.)
Example:
A program’s running time varies with the square of the input size.
If it takes 1 second to handle an operation involving 10 records, how long will it take to handle 20 records?
How about 100 records?
100 seconds
How about 1,000 records?
10,000 seconds (~3 hours)
Program Running Times (cont.)
How about 10,000 records?
Almost 2 weeks!!
Even if we double the speed of the computer, it will “only” take a week!!
The only way to really speed things up is to reduce the running time, Growth Rate.
Growth Rates
We use an input size N to compute  growth rates
Idea: Assume system-dependent differences are constant for the algorithms
Use an idealized computer
For this we use the notation...

OH!
Big O Notation
O(1), or constant
O(logN), or logarithmic (base 2)
O(N), or linear (directly proportional to   N)
O(N log N), or (usually just called N log   N)
O(N2), or quadratic (proportional to the square of N)
Estimation
Sequence of instructions
Decision branching
Loops
Subroutine calls
Sequence of Instructions
Simple statement:
a := 332.3;
O(1)
Sequence of statements:
Temp := a;
a := b;
b := a;
Decision Statements
Estimate conservatively
Take the worst case
IF x > y THEN
   Max := x;
ELSE
   Max := y;
END IF;
Loop Structures
Sum each step through the loop
FOR  i   IN   p .. q   LOOP
   x := x + i;
END LOOP;

Subroutine Calls
Just compute the Big O of the subroutine, and include it in our computation
Rule of Sums
T1(n) and T2(n) are the running times of two code segments P1 and P2.
Then T1(n) + T2(n), the running time of P1 followed by the running time of P2, is O(max(f(n),g(n))
Rule of Products
The running times of T1(n) and T2(n) are O(f(n))  and O(g(n)).
Then T1(n)T2(n) is O(f(n)g(n))
For loops
Counting Loops
Counting Loops are usually O(N)
Nested counting loops are usually O(N2)
FOR i IN 1 .. N LOOP
  FOR j IN 1 .. i LOOP
    --Something O(1) performace
  END LOOP;
END LOOP;
Running Time?
Counting Loops (cont.)
FOR i IN 1 .. N LOOP
  FOR j IN i .. N LOOP
    --Something O(1) performace
  END LOOP;
END LOOP;

Running Time?
Multiplicatively Conrolled Loops
Control := 1;
WHILE Control <= N LOOP
  --Something O(1) performace
  Control := Control * 2;
END LOOP;

Running Time?
Multiplicatively Conrolled Loops (cont.)
Control := N;
WHILE Control >= 1 LOOP
  --Something O(1) performace
  Control := Control / 2;
END LOOP;

Running Time?
Nesting
FOR i IN 1 .. N LOOP
  Control := 1;
  WHILE Control <= N LOOP
    --Something O(1) performace
    Control := Control * 2;
  END LOOP;
END LOOP;
Running Time?
Nesting (cont.)
Control := N;
WHILE Control >= 1 LOOP
  FOR i IN 1 .. N LOOP
   --Something O(1) performace
  END LOOP;
  Control := Control / 2;
END LOOP;
Running Time?
Factorial Revisited
Can we rewrite factorial iteratively?
Does the Running Time change?

Flip Revisited
What is the Running Time?

Permutations
Start with a set in the order { A, B, C, D }
Print A, Followed by all permutations of { B, C, D }
Interchange A and B, print B followed by all permutations of { A, C, D }
Interchange B and C, print C followed by all permutations of { A, B, D }
Interchange C and D, print D followed by all permutations of { A, B, C }
Permutations (cont.)
Running Time?
Can we rewrite this iteratively?
Recursive Binary Search
Divide your list in half
If the name is the same as the middle one, we are done
If the name is earlier in the alphabet, then make the first half your new list
If the name is later, then make the second half your new list
Repeat until done
Recursive Binary Search (cont.)
Running Time?
Can we rewrite this iteratively?
An ADT for Keyed Tables
Table Operations:
InitializeTable: Creates an empty table
Insert: Adds a new element to the table
Delete: Removes an element from the table
Retrieve: Returns a copy of an element, given its key
Traverse: Displays all the elements sorted by key
Implementation 1:Unordered Array
Running Time for Operations?
InitializeTable? (Set CurrentSize to 0)
Insert? (Add element to end of list)
Delete? (Search for element, delete it, shift all other elements forward on space)
Retrieve? (Search for element, return it)
Traverse? (Sort list, output sorted list)
Implementation 2:Ordered Array
Running Time for Operations?
InitializeTable? (Set CurrentSize to 0)
Insert? (Find proper place, shift all other elements back one space)
Delete? (Search for element, shift all other elements forward one space)
Retrieve? (Search for element, return it)
Traverse? (Output sorted list)
Comparison of Running Times