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
• Design

1. If the string is of length zero or one, return string
2. For any other string:
   1. Recursively call the function with the first character removed
   2. Concatenate to the result of the character that was removed

• The Code

public String reverse(String str) {
  String result;
  if (str.length() <= 1) {
    result = str;
  } else {
    result = reverse(str.substring(1)) + str.substring(0,1);
  }
  return result;
}

Arrays

• Arrays are an ordered collection of values
  • They are objects in Java (not in C++)
  • Their size is immutable
  • Arrays start at position zero
• Arrays allow us to refer to an entire collection of data using a single variable name
• We can access individual values using an index variable
• Creation:

typeOfValue[] referenceVar;
referenceVar = new typeOfValue[size];

• Example:

int[] iArray; // creates a reference to an array of integer values
iArray = new int[3]; // creates actual array & assigns it to iArray

Problem

• Compute the sum of the elements in an int valued array
• Analysis:
  • Inputs: an array of int values
  • Outputs: An integer of the sum of all values
  • Constraints: None
  • Assumptions: Array does not change
  • Relationships: none
• Design:
  • Given an array, the array's length, index of current element

1. If array's length is less than or equal to the index then return zero
2. Otherwise
   1. Recur with index plus one
   2. Compute and return sum of the element at index and recursive's returned value

Code

class ArraySum {
  public int elementSum(int[] a) {
    return doElementSum(a, 0);
  }

  private int doElementSum(int[] a, int index) {
    int sum;
    if (a.length <= index) {
      sum = 0;
    } else {
      sum = a[index] + doElementSum(a, index+1);
    }
    return sum;
  }
}

Array of Arrays

• It is possible to construct arrays with multiple dimensions:

int[][] a = {{1,2,3},{4,5,6},{7,8,9}};

• Alternative way to declare:

int[][] a = new int[3][];
a[0] = new int[3];
a[1] = new int[3];
a[2] = new int[3];
a[0][0] = 1;
a[0][1] = 2;
a[0][2] = 3;
a[1][0] = 4;
...

• Note: Each row can be a different length

Array Searching

• Suppose that we want to know the position of the largest value in an array (the last position, if multiple occurrences)
• We could search linearly to find it
• Possible approach:

1. Assume value in position 0 is largest
2. Compare to next value:
   1. If no more values, done
   2. If next value is larger or equal, make it the largest so far
   3. If next value is smaller, repeat

Code

public int posOfLargest(int[] a, int pol, int index) {
  int result;
  if (index >= a.length) {
    result = pol;
  } else if (a[pol] > a[index]) {
    result = posOfLargest(a, pol, index+1);
  } else {
    result = posOfLargest(a, index, index+1);
  }
  return result;
}