7 Analysis of Algorithms

Version 6¹

Code listings, handouts: Three Algorithms for Analysis

7.1 Timing

• Measuring time with System.currentTimeMillis() (see TimeTest.java, Fig. 7-1 and 7-2, pp. 184–185).
• Typically we need to repeat the operation being timed because the computer is so fast.
• Results are subject to random variations caused by other processes on the system, so repeat the experiment several times—or several million times—and take an average.
• The results of the example suggest the ArrayList class has a faster get method than the LinkedList class, and that in the latter, get(i) has time proportional to i; but "a couple of data points are not really a convincing case."
• And we do not want to collect hundreds of data points, either, so we'll use some math to simplify the problem.

Additional Notes

• The Linux shell command time can also be used to measure the time to run a program:

  $ java TimeTest
  ArrayList: 7 milliseconds
  LinkedList: 22 milliseconds
  
  $ time java TimeTest
  ArrayList: 7 milliseconds
  LinkedList: 51 milliseconds
  
  real    0m0.234s
  user    0m0.111s
  sys     0m0.020s
  

• The program's CPU time is user + sys. (sys is the time spent by the operating system on behalf of the program.) This includes time to start the Java program running (start up Java Virtual Machine, load classes), so it is larger, but it does not include time during which the CPU works on other processes (which real time does).

7.2 Asymptotic Notation

• Note for users of dysfunctional browsers:
  • Θ should display as the Greek capital letter Theta (looks like an O with a horizontal bar).
  • Ω should display as Greek capital Omega (looks like an upside-down U with feet).
  • ⇔ should display as a bidirectional double-lined arrow, meaning "if and only if."
  • ≤ and ≥ should display as the symbols for "less than or equal to" and "greater than or equal to", respectively.
  • ⋅ should display as a centered dot, the multiplication sign.
• Importance of the time "for large N"
  • But not always.
• Time as a property of the algorithm, not its implementation.
• To keep our eyes on what's important, we abstract away certain details: T(N) = 10 N² − 5N + 75 = aN² + bN + c = Θ(N²)
• Pronounce Θ(f) as "[the] order [of] f". Orders are the sets of functions of interest—what's left after abstracting away the details.
• Intuitively, an order is a set of functions with the same rate of growth. To say f is lower order than g means that f(N) grows less rapidly than g(N) as N increases (for large values of N).
• (Important) Common orders and their names: Fig. 7-5 p. 189:
  • Arranged from high (Θ(2^N)) to low (Θ(1)).
  • Add exponential = Θ(2^N).
  • How to remember the place of Θ(N log N):
    1. For large N, 1 < log N < N.
    2. Multiplying all parts of that inequality by N yields: N < N log N < N ²
• Some mathematical properties of orders (f, g, h are functions):
  • If g is f multiplied or divided by a positive constant, then Θ(g) = Θ(f).
  • If h is lower order than f, and g = f + h or g = f − h, then Θ(g) = Θ(f).
  • Examples:
    • N², 10.5 N²
    • N², N² + N
    • N², N² + N + 1
• Sometimes we cannot show that the running time function's order is equal to a known order, but we can show that it is ≤ or ≥ a known order.
  • Example: Θ(N!) ≥ Θ(2^N)
• This is so common that there is special notation:
  • Ω(f) is the set of all functions of equal or higher order than f, i.e., {g | Θ(g) ≥ Θ(f)}.
  • O(f) is the set of all functions of equal or lower order than f, i.e., {g | Θ(g) ≤ Θ(f)}.
  • Θ(f) is the set of functions of equal order to f. It is, in fact, the intersection of Ω(f) and O(f).
• Formal definitions:
  • f is in O(g) ⇔ for some c > 0, for some N₀ ≥ 0, for all N ≥ N₀, f(N) < cg(N). [should < be ≤?]
  • f is in Ω(g) ⇔ for some c > 0, for some N₀ ≥ 0, for all N ≥ N₀, f(N) > cg(N). [should > be ≥?]
  • f is in Θ(g) ⇔ f is in O(g) and f is in Ω(g).
• Terminology:
  • Asymptotic (upper / lower/ tight) bound (Ω, O, Θ).
• Diagrams ...
• Print errors: last paragraph on p. 191.
• Exercises p. 191: #7.5, #7.2–7.5

7.3 Counting Steps

• What is a step (p. 192–193)? [Anything that takes constant time, Θ(1), including a fixed sequence of steps.]
  • Java operators: 1 step each.
  • Java methods: possibly more than one step.
• The process of analysis:
  • For each line, figure the number of steps on the line.
  • Multiply by the number of repetitions of that line.
  • Sum the steps for all lines of code.
• Exercises:
  • p. 197 #7.9; possibly 7.10 or another similar problem. *** We need a better example as a problem to work out.
  • Three algorithms for analysis. See algorithms 1 and 2.

7.4 Best, Worst, and Average Case Analysis

• How would we analyze the time of an algorithm that uses an if statement, where the two branches have unequal times?
• Best case: assume best branch is taken.
• Worst case: assume worst branch is taken.
• Average case: P(worst) ⋅ Time(worst) + P(best) ⋅ Time(best).
  • Average case analysis is more difficult, partly because we need to know the probabilities of each path, and partly because of the more complex math.
  • Know what it is, but we will not do it in this class.
• Example: Three algorithms for analysis. See algorithm 3.

7.5 Amortized Analysis

• Investigates the worst possible total time for a sequence of runs (this is typically for a function or method within a larger program), and reports the average time of these runs. — This is not the same as the average case!
• "amortize: ... 2. Accounting: To write off (expenditures) by prorating over a certain period." (Amer. Heritage Dictionary)
• Example: the ArrayList add method
  1. Worst possible sequence of N runs: start with empty list, with capacity 1, keep adding until N additions have been made, without deleting anything.
  2. Figure the total time including list copying (Fig. 7-20 p. 200).
  3. Divide the cost of the expensive operation (stretch) among the runs.
• A more intuitive approach: After stretching the array by copying N elements, the next time we stretch it we will have to copy 2N elements, but the time until that happens is twice as long, so on the average it's constant. More precisely, the time for N additions is at worst Θ(N).
• Amortized analysis distributes the expensive operations over the number of "runs" that leads up to them.
• Exercise: p. 202, #7.15. Just do it intuitively.

Footnotes