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.