# 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:

• If f(N) is a sum of several terms, the highest order term (the one with the fastest growth rate) is kept and others are discarded.
• If f(N) has a term that is a product of several factors, all constants (those that are not in terms of N) are omitted.

### 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³)

### 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 complexities for various code examples.  ### 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.
exponential