CIS 3020 Part 7

Complexity

• When computing O(), we are concerned with big values of n
• With big values, constants become ignorable
• Consider the two exponential functions we developed
• Let's count all operations (arithmetic, assignment, references, comparisons, etc.) the same with calls counting 20.

Exponentiation, O(N)

public int expt(int b, int n) { int result; if (n<=0) { result = 1; } else { result = b * expt(b, n-1); } return result; }

2 1 3 3 28 2 ------ 39

Exponentiation, O(log N)

public int expt(int b, int n) { return fastExpt(b,n); } private int fastExpt(int b, int n) { int result; if (n<=0) result = 1; else if (even(n)) result = square(fastExpt(b, n/2)); else result = b * fastExpt(b, n-1); return result; } private int square(int x) { return (x * x); } private boolean even(int x) { return (x % 2 == 0); }

2 23 2 1 6 67 28 2 1 4 1 6 ------ 143

Comparison

• some might argue that the second method is ~3.7 times as expensive
• And, even if it is O(log N), it will be slower than the first method
• Let's look at values to see if this is true...

N	O(N)	O(log N)	39*O(N)	143*O(log N)
2	2	1	78	143
4	4	2	156	286
8	8	3	312	429
16	16	4	624	572
32	32	5	1248	715
64	64	6	2496	858
128	128	7	4992	1001
256	256	8	9984	1144
512	512	9	19968	1287
1024	1024	10	39936	1430

String Reversal

• Suppose that we would like to reverse the characters in a string: "Theory" becomes "yroehT"
• Analysis:
  • Inputs: String
  • Outputs: String
  • Constraints: input and output strings contain some characters, output in reverse order of input
  • Assumptions: none
  • Relationships: none
• For what group of strings do we immediately know a solution?
  • Strings consisting of a single character
  • Strings consisting of no characters
• These define our base cases
• How can we work towards these base cases?

1. Remove first character
2. Reverse the rest of the string
3. Add the first character to the end

• • This defines our recursive case