Linear Complexity - O(n)
Understand how linear time complexity O(n) works by examining how an algorithm's runtime increases proportionally with input size, such as looping over arrays in JavaScript. This lesson helps you grasp the practical implications of linear complexity in algorithm design and prepares you for more complex concepts like quadratic time complexity.
We'll cover the following...
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.