Linear Complexity - O(n)

If an algorithm’s time complexity is linear, it means that the runtime of the algorithm grows almost linearly with the input size. A typical example of this, is by looping over an array. The more elements there are in the array, the longer it takes to finish looping! Let’s say that we invoke a function on every element in the array. The function takes 5ms to execute.

The time it takes to execute is directly dependent on the size of the input! In a graph, it would look like this:

In the next lesson, I will talk about algorithms having a quadratic time complexity.