Class 25: Algorithm Analysis (2)

Held: Friday, 8 October 2004

Summary: Today we formalize techniques for comparatively evaluating the running time of algorithms.

Related Pages:

• EBoard.
• Sample Code.

Notes:

• Are there questions on the homework?
• Warning! Lots of Math today. (It will get better after break.)

Overview:

• Example, revisited.
• Asymptotic Analysis.
• Asymptotic Analysis in Practice.

Asymptotic Analysis

• Noting problems in providing a precise analysis of the running time of programs, computer scientists developed a technique which is often called asymptotic analysis. In asymptotic analysis of algorithms, one describes the general behavior of algorithms in terms of the size of input, but without delving into precise details.
  • The analysis is asymptotic in that we look at the behavior as the input gets larger.
• There are many issues to consider in analyzing the asymptotic behavior of a program. One particularly useful metric is an upper bound on the running time of an algorithm. We call this the Big-O of an algorithm.
• Informally, Big-O gives the general shape of the curve of the graph of running time vs. input size.
  • That is, is it linear, quadratic, logarythmic, ...
• Big-O is defined somewhat mathematically, as a relationship between functions.
• f(n) is in O(g(n)) iff
  • there exists a number n₀
  • there exists a number d > 0
  • for all but finitely many n > n₀, abs(f(n)) <= abs(d*g(n))
• What does this say? It says that after a certain value, n₀, f(n) is bounded above by a constant (that is, d) times g(n).
  • The constant, d, helps accommodate the variation in the algorithm.
  • We don't usually identify the d precisely.
  • The n₀ says for big enough n.
• We can apply big-O to algorithms.
  • n is the size of the input (e.g., the number of items in a list or vector to be manipulated).
  • f(n) is the running time of the algorithm.
• Some common Big-O bounds
  • An algorithm that is in O(1) takes constant time. That is, the running time is independent of the input. Getting the size of a vector should be an O(1) algorithm.
  • An algorithm that is in O(n) takes time linear in the size of the input. That is, we basically do constant work for each element of the input. Finding the smallest element in a list is often an O(n) algorithm.
  • An algorithm that is in O(log₂(n)) takes logarithmic time. While the running time is dependent on the size of the input, it is clear that not every element of the input is processed. Many such algorithms involve the strategy of divide and conquer.

Asymptotic Analysis in Practice

• We now have a theoretical grounding for asymptotic analysis. How do we do it in practice?
• For iterative algorithms, it's often best to count the steps in an algorithm and then add them up.
  • Assume most things take one step.
  • If you call a function, you'll need to analyze the running time of that function
  • For loops, analyze the body of the loop and then multiply by the number of times the loop repeates.
  • For conditionals, analyze the two halves of the conditional and take the largest.
• We may find other ways to count, too.
• After you've taken combinatorics, you can use recurrence relations for recursive functions.
  • We may do some informal recurrence relations.
• Over the next few days, we'll look at a number of examples. Some starting ones.
  • Finding the smallest/largest element in a vector of integers.
  • Finding the average of all the elements in a vector of integers.
  • Putting the largest element in an array at the end of the array. if we're only allowed to swap subsequent elements.
  • Binary search
  • ...