2.6 O notation

Big O notation

Big O notation is a mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size. In Big O notation, all functions that have the same growth rate (as determined by the highest order term of the function) are characterized using the same Big O notation. In essence, all functions that have the same growth rate are considered equivalent in Big O notation.

Given a function that describes the running time of an algorithm, the Big O notation for that function can be determined using the following rules:

Activity 1: Big O notation.

  1. Which of the following Big O notations is equivalent to O(N+9999)?
    O(1)
    O(N)
    O(9999)


  2. Which of the following Big O notations is equivalent to O(734·N)?
    O(N)
    O(734)
    O(734·N²)


  3. Which of the following Big O notations is equivalent to O(12·N +6·N³ + 1000)?
    O(1000)
    O(N)
    O(N³)


Big O notation of composite functions

The following rules are used to determine the Big O notation of composite functions: c denotes a constant

image1

Activity 2: Big O notation for composite functions.

Determine the simplified Big O notation.

  1. 10 · O(N²)
    O(10)
    O(N²)
    O(10 · N²)


  2. 10 + O(N²)
    O1
    O(N²)
    O(10 + N²)


  3. 3·N · O(N²)
    O(N²)
    O(3·N²)
    O(N³)


  4. 2·N³ + O(N²)
    O(N²)
    O(N³)
    O(N² + N³)


Runtime growth rate

One consideration in evaluating algorithms is that the efficiency of the algorithm is most critical for large input sizes. Small inputs are likely to result in fast running times because N is small, so efficiency is less of a concern. The table below shows the runtime to perform f(N) instructions for different functions f and different values of N. For large N, the difference in computation time varies greatly with the rate of growth of the function f. The data assumes that a single instruction takes 1 μs to execute.

image2

Common Big O complexities

Many commonly used algorithms have running time functions that belong to one of a handful of growth functions. These common Big O notations are summarized in the following table. The table shows the Big O notation, the common word used to describe algorithms that belong to that notation, and an example with source code. Clearly, the best algorithm is one that has constant time complexity. Unfortunately, not all problems can be solved using constant complexity algorithms. In fact, in many cases, computer scientists have proven that certain types of problems can only be solved using quadratic or exponential algorithms.

Runtime complexities for various code examples.

image3 image4

Activity 3: Big O notation and growth rates.

  1. O(5) has a _____ runtime complexity.
    constant
    linear
    exponential


  2. O(N log N) has a _____ runtime complexity.
    constant
    linearithmic
    logarithmic


  3. O(N + N²) has a _____ runtime complexity.
    linear-quadratic
    exponential
    quadratic


  4. A linear search has a _____ runtime complexity.
    O(log N)
    O(N)
    O(N²)


  5. A selection sort has a _____ runtime complexity.
    O(N)
    O(N log N)
    O(N²)