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:
- find the fastest growing term (which is an since b is constant)
- 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.