nix

• An efficient algorithm for sorting a small number of elements, sorted in place.
• INSERTION-SORT(A) /* A[1 ‥ n], (c₁n²) */
  

• Figure 2.2: The operation of INSERTION-SORT

            

• The subarray consisting of elements A[1 ‥ j - 1] are the elements originally in positions 1 through j - 1, but now in sorted order, and elements A[j + 1 ‥ n] correspond to the pile of cards still on the table.

            

• Loop invariant:
  • Initialization: It is true prior to the first iteration of the loop.
  • Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
  • Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

• Analyzing an algorithm has come to mean predicting the resources (computational time, memory, communication bandwidth, or hardware) that the algorithm requires.
• Mathematical induction, prove a base case and an inductive step.
• Before we can analyze an algorithm, we must have a model of the implementation technology that will be used, including a model for the resources of that technology and their costs.
• The RAM (random-access machine) model contains instructions commonly found in real computers: arithmetic (add, subtract, multiply, divide, remainder, floor, ceiling), data movement (load, store, copy), and control (conditional and unconditional branch, subroutine call and return). Each such instruction takes a constant amount of time.
• Kinds of analyses
  • Worst-case: (usually)
    • T(n) = maximum time of algorithm on any input of size n.
  • Average-case: (sometimes)
    • T(n) = expected time of algorithm over all inputs of size n.
    • Need assumption of statistical distribution of inputs.
  • Best-case: (bogus)
    • Cheat with a slow algorithm that works fast on some input.
• The worst-case running time of an algorithm is an upper bound on the running time for any input.
• Asymptotic analysis:
  • Look at growth of T(n) as n → ∞ .
• Θ-notation: Θ(g(n)) = {f(n) : there exist positive constants c₁, c₂, and n₀ such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀}.   /* c₁, c₂, n₀ > 0 */
  Drop low-order terms; ignore leading constants.
  Example: 3n³ + 90n² – 5n + 6046 = Θ(n³)
• Asymptotic performance: When n gets large enough, a Θ(n²) algorithm always beats a Θ(n³) algorithm.

            

• Insertion sort analysis
  • Worst case: Input reverse sorted. T(n) = ∑_j=2 ^j=n θ(j) = θ(n²)
  • Average case: All permutations equally likely. T(n) = ∑_j=2^j=n θ(j/2) = θ(n²)

• Divide-and-conquer approach breaks the problem into several (independent) subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.
  • Divide the problem into a number of subproblems.
  • Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
  • Combine the solutions to the subproblems into the solution for the original problem.
• MERGE(A, p, q, r) 
  

/* p ≤ q < r, A[p ‥ q] and A[q + 1 ‥ r] are in sorted order, Θ(n) */

• Figure 2.3: The operation of MERGE(A, 9, 12, 16).

            

• MERGE-SORT(A, p, r)   /* Worst case: O(n lg n) */

• Figure 2.4: The operation of merge sort on the array A = 〈5, 2, 4, 7, 1, 3, 2, 6〉.

            

• When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence equation or recurrence.
• A recurrence for the running time of a divide-and-conquer algorithm is based on the three steps of the basic paradigm. Let T (n) be the running time on a problem of size n. Suppose that the division of the problem yields a subproblems, each of which is 1/b the size of the original. If we take D(n) time to divide the problem into subproblems and C(n) time to combine the solutions to the subproblems into the solution to the original problem, we get the recurrence.

            

• Analysis of merge sort
  • Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = Θ(1).
  • Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T (n/2) to the running time.
  • Combine: We have already noted that the MERGE procedure on an n-element subarray takes time Θ(n), so C(n) = Θ(n).

                        
                        

• Figure 2.5: The construction of a recursion tree for the recurrence T(n) = 2T(n/2) + cn. The fully expanded tree has lg n + 1 levels, and each level contributes a total cost of cn. The total cost is cn lg n + cn, which is Θ(n lg n).