Topic Number 2 Efficiency – Complexity Algorithm Analysis

Significant Improvement – Algorithm with Smaller Big O function

• CS 314

• Efficiency - Complexity

• Problem: Given an array of ints replace any element equal to 0 with the maximum positive value to the right of that element. (if no positive value to the right, leave unchanged.)
• Given:
• [0, 9, 0, 13, 0, 0, 7, 1, -1, 0, 1, 0]
• Becomes:
• [13, 9, 13, 13, 7, 7, 7, 1, -1, 1, 1, 0]

Replace Zeros – Typical Solution

• public void replace0s(int[] data){ for(int i = 0; i < data.length; i++){
• if (data[i] == 0) {
• int max = 0;
• for(int j = i+1; j
• data[i] = max; }
• }
• }
• Assume all values are zeros. (worst case)
• Example of a dependent loops.
• Clicker 10 - Number of times j < data.length evaluated?
• O(1) B. O(N) C. O(NlogN)
• D. O(N2) E. O(N!)

Replace Zeros – Alternate Solution

• CS 314

• Efficiency - Complexity

• public void replace0s(int[] data){ int max = Math.max(0, data[data.length – 1]);
• int start = data.length – 2;
• for (int i = start; i >= 0; i--) {
• if (data[i] == 0)
• data[i] = max;
• else
• max = Math.max(max, data[i]);
• }
• }
• Clicker 11 - Big O of this approach?
• O(1) B. O(N) C. O(NlogN)
• D. O(N2) E. O(N!)

Clicker 12

• Is O(N) really that much faster than O(N2)?
• never
• always
• typically
• Depends on the actual functions and the value of N.
• 1000N + 250 compared to N2 + 10
• When do we use mechanized computation?
• N = 100,000
• 100,000,250 < 10,000,000,010 (108 < 1010)