What is Big O Notation and Time Complexity?

Given an array = [1, 3, 4, 5, ..., 11], if we have a function, e,g, such as the one for finding the sum of this array:

---

def find_sum(array):
    total = 0
    for each i in array:
        total += i
    return total

---

we often would like to understand/describe the complexity of the function we've wrote, which can be done with the concept of time complexity and big O notation.


Time Complexity is a way of showing how the runtime of a function increases as the size of the input increases, there are different types of time complexity such as:

• linear time complexity
• constant time complexity (stays as a constant)
• quadratic time complexity

Big O Notation expresses in a mathimetical way.

• linear time complexity: $O(n)$
• constant time complexity (stays as a constant): $O(1)$
• quadratic time complexity: $O(n^2)$

For example, the time T of the find_sum function in terms of the number of input n can be expressed as:

$T=an+b$

To derive the big O notation based on this expression, follow two steps:

1. find the fastest growing term (which is an since b is constant)
2. take out the coefficient (which is a in an, and n is left -> $O(n)$)

So the problem left is how to derive the expression for $T=an+b$, a simple approach by line by line can be described as follows:

---

def find_sum(array):
    total = 0 -> $O(1)$
    for each i in array: -> this line and the following will result in $O(n)$
        total += i -> $O(1)$
    return total -> $O(1)$

---

So the total $T=O(1)+n \times O(1) + O(1)$, which can be expressed as $T=an+b$ where b denotes the constant for two $O(1)$s.


For more details, have a look at the excellent video from CS Dojo.