2.7 Algorithm analysis

Worst-case algorithm analysis

To analyze how runtime of an algorithm scales as the input size increases, we first determine how many operations the algorithm executes for a specific input size, N. Then, the big-O notation for that function is determined. Algorithm runtime analysis often focuses on the worst-case runtime complexity. The worst-case runtime of an algorithm is the runtime complexity for an input that results in the longest execution. Other runtime analyses include best-case runtime and average-case runtime. Determining the average-case runtime requires knowledge of the statistical properties of the expected data inputs.

Activity 1: Worst-case runtime analysis.

  1. Which function best represents the number of operations in the worst-case?
    imageq1
    f(N) = 3N + 2
    f(N) = 3N + 3
    f(N) = 2 + N (N + 1)


  2. What is the big-O notation for the worst-case runtime?
    imageq2

    f(N) = 2 + 4N + 1
    O(4N + 3)
    O(N)


  3. What is the big-O notation for the worst-case runtime?
    imageq3

    O(1)
    O(N2)
    O(N)


  4. What is the big-O notation for the worst-case runtime?
    imageq4

    O(log N)
    O(N2)
    O(N)


  5. What is the big-O notation for the best-case runtime?
    imageq5

    O(1)
    O(N)


Counting constant time operations

For algorithm analysis, the definition of a single operation does not need to be precise. An operation can be any statement (or constant number of statements) that has a constant runtime complexity, O(1). Since constants are omitted in big-O notation, any constant number of constant time operations is O(1). So, precisely counting the number of constant time operations in a finite sequence is not needed. Ex: An algorithm with a single loop that execute 5 operations before the loop, 3 operations each loop iteration, and 6 operations after the loop would have a runtime of f(N) = 5 + 3N + 6, which can be written as O(1) + O(N) + O(1) = O(N). If the number of operations before the loop was 100, the big-O notation for those operation is still O(1).

Activity 2: Constant time operations.

  1. A for loop of the form for (i = 0; i < N; ++i) {} that does not have nested loops or function calls, and does not modify i in the loop will always has a complexity of O(N).
    True
    False


  2. The complexity of the algorithm below is O(1).
    imageq7

    True
    False


  3. The complexity of the algorithm below is O(1).
    imageq8

    True
    False


Runtime analysis of nested loops

Runtime analysis for nested loops requires summing the runtime of the inner loop over each outer loop iteration. The resulting summation can be simplified to determine the big-O notation.

image1

Activity 3: Nested loops.

Determine the big-O worst-case runtime for each algorithm.

  1. imageq9
    O(N)
    O(N²)


  2. imageq10
    O(N)
    O(N²)


  3. imageq11
    O(N)
    O(N²)


  4. imageq12
    O(N²)
    O(N³)


  5. imageq13
    O(N)
    O(N²)
    O(N³)