2. Algorithm Analysis Part 2

2.1. Growth Rate Example (1)

Example 1: Find largest value

// Return position of largest value in integer array A
static int largest(int[] A) {
  int currlarge = 0;             // Position of largest element seen
  for (int i=1; i<A.length; i++) // For each element
    if (A[currlarge] < A[i])     //   if A[i] is larger
       currlarge = i;            //     remember its position
  return currlarge;              // Return largest position
}

2.2. Growth Rate Example (2)

Example 2: Assignment statement

Example 3: Double loop

sum = 0;
for (j=1; j<=n; j++) {     // First for loop
  for (i=1; i<=j; i++) {  //   is a double loop
    sum++;
  }
}
for (k=0; k<n; k++) {      // Second for loop
   A[k] = k;
}

2.3. Growth Rate Graph (1)

2.4. Growth Rate Graph (2)

2.5. Best, Worst, Average Cases

  • Not all inputs of a given size take the same time to run.

    • Sequential search for K in an array of \(n\) integers:

    • Begin at first element in array and look at each element in turn until K is found

      • Best case:

      • Worst case:

      • Average case:

2.6. Which Analysis to Use?

  • While average time appears to be the fairest measure, it may be difficult to determine.

  • When is the worst case time important?

2.7. Faster Computer or Algorithm?

Suppose we buy a computer 10 times faster.

\[\begin{split}\begin{array} {l|r|r|l|r} \mathbf{f(n)} & \mathbf{n} & \mathbf{n'} & \mathbf{Change} & \mathbf{n'/n}\\ \hline 10n & 1000 & 10,000 & n' = 10n & 10\\ 20n & 500 & 5000 & n' = 10n & 10\\ 5 n \log n & 250 & 1842 & \sqrt{10} n < n' < 10n & 7.37\\ 2 n^2 & 70 & 223 & n' = \sqrt{10} n & 3.16\\ 2^n & 13 & 16 & n' = n + 3 & --\\ \end{array}\end{split}\]

  • \(n\): size of input that can be processed in one second on old computer (in 1000 computational units)

  • \(n'\): size of input that can be processed in one second on new computer (in 10,000 computational units)

2.8. Asymptotic Analysis: Big-oh

  • Definition: For \(\mathbf{T}(n)\) a non-negatively valued function, \(\mathbf{T}(n)\) is in the set \(O(f(n))\) if there exist two positive constants \(c\) and \(n_0\) such that \(T(n) \leq cf(n)\) for all \(n > n_0\).

  • Use: The algorithm is in \(O(n^2)\) in [best, average, worst] case.

  • Meaning: For all data sets big enough (i.e., \(n>n_0\)), the algorithm always executes in less than \(cf(n)\) steps in the [best, average, worst] case.

2.9. Big-oh Notation (cont)

  • Big-oh notation indicates an upper bound.

  • Example: If \(\mathbf{T}(n) = 3n^2\) then \(\mathbf{T}(n)\) is in \(O(n^2)\).

  • Look for the tightest upper bound:

    • While \(\mathbf{T}(n) = 3n^2\) is in \(O(n^3)\), we prefer \(O(n^2)\).

2.10. Big-Oh Examples

  • Example 1: Finding value X in an array (average cost).

    • Then \(\textbf{T}(n) = c_{s}n/2\).

    • For all values of \(n > 1, c_{s}n/2 \leq c_{s}n\).

    • Therefore, the definition is satisfied for \(f(n)=n, n_0 = 1\), and \(c = c_s\). Hence, \(\textbf{T}(n)\) is in \(O(n)\).

2.11. Big-Oh Examples (2)

  • Example 2: Suppose \(\textbf{T}(n) = c_{1}n^2 + c_{2}n\), where \(c_1\) and \(c_2\) are positive.

    • \(c_{1}n^2 + c_{2}n \leq c_{1}n^2 + c_{2}n^2 \leq (c_1 + c_2)n^2\) for all \(n > 1\).

    • Then \(\textbf{T}(n) \leq cn^2\) whenever \(n > n_0\), for \(c = c_1 + c_2\) and \(n_0 = 1\).

    • Therefore, \(\textbf{T}(n)\) is in \(O(n^2)\) by definition.

  • Example 3: \(\textbf{T}(n) = c\). Then \(\textbf{T}(n)\) is in \(O(1)\).

2.12. A Common Misunderstanding

  • “The best case for my algorithm is n=1 because that is the fastest.”

  • WRONG!

  • Big-oh refers to a growth rate as n grows to \(\infty\)

  • Best case is defined for the input of size n that is cheapest among all inputs of the same size \(n\).

2.13. Big \(\Omega\)

  • Definition: For \(\textbf{T}(n)\) a non-negatively valued function, \(\textbf{T}(n)\) is in the set \(\Omega(g(n))\) if there exist two positive constants \(c\) and \(n_0\) such that \(\textbf{T}(n) \geq cg(n)\) for all \(n > n_0\).

  • Meaning: For all data sets big enough (i.e., \(n > n_0\)), the algorithm always requires more than \(cg(n)\) steps.

  • Lower bound.

2.14. Big-Omega Example

  • \(\textbf{T}(n) = c_1n^2 + c_2n\).

    • \(c_1n^2 + c_2n \geq c_1n^2\) for all \(n > 1\).

    • \(\textbf{T}(n) \geq cn^2\) for \(c = c_1\) and \(n_0 = 1\).

    • Therefore, \(\textbf{T}(n)\) is in \(\Omega(n^2)\) by the definition.

  • We want the greatest lower bound.

2.15. \(\Theta\) Notation

  • When big-Oh and \(\Omega\) coincide, we indicate this by using \(\Theta\) (big-Theta) notation.

  • Definition: An algorithm is said to be in \(\Theta(h(n))\) if it is in \(O(h(n))\) and it is in \(\Omega(h(n))\).

2.16. A Common Misunderstanding

  • Confusing worst case with upper bound.

  • Upper bound refers to a growth rate.

  • Worst case refers to the worst input from among the choices for possible inputs of a given size.

2.17. Simplifying Rules

  1. If \(f(n)\) is in \(O(g(n))\) and \(g(n)\) is in \(O(h(n))\), then \(f(n)\) is in \(O(h(n))\).

  2. If \(f(n)\) is in \(O(kg(n))\) for some constant \(k > 0\), then \(f(n)\) is in \(O(g(n))\).

  3. If \(f_1(n)\) is in \(O(g_1(n))\) and \(f_2(n)\) is in \(O(g_2(n))\), then \((f_1 + f_2)(n)\) is in \(O(\max(g_1(n), g_2(n)))\).

  4. If \(f_1(n)\) is in \(O(g_1(n))\) and \(f_2(n)\) is in \(O(g_2(n))\), then \(f_1(n)f_2(n)\) is in \(O(g_1(n)g_2(n))\).

2.18. Summary (1)

  • If we fix the size of \(n\)

    • TOH only has one input of any given size \(n\).

    • Findmax has the same cost (in terms of number of records viewed) for all inputs of size \(n\).

    • Find a value has different costs for different arrangements of the values in the array (ranging from 1 to n).

2.19. Summary (2)