Linear Time Complexity Explained
Understanding Big O Notation.
Have you ever written a for loop?
let’s refresh our memory
How many times do you think this loop runs?
Five times — Great. (Because we have five elements in the list)
what about this?
10 times. Great!!!! (Because we have 10 elements in the list)
That was easy, right?
Let’s make it complicated.
How many times does this loop run if we have to find ‘e’?
If your answer is 5, thats awesome. You are right.
But if we had to find ‘j’ in the list [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’]
How many times will the loop run?
Ten times, Great.
Ok, we have started seeing a pattern here now.
With this approach, we can find an element in 10 or fewer steps. Because we have 10 elements in the list, finding an element in that loop will take us at most 10 times.
Now, if we take this Step as the measure of time that takes to find an element in the list, then the time would be 1 for ‘a’, 2 for ‘b’, 10 for ‘j’ and so on.
Meaning ‘j’ would take the most time, ( ‘j’ would take a longest time (step) to be found-10 cause ‘j’ hiding in the back of the list)
At worst it would take us 10 tries to find an element, but at best we can find it in 1 step.
Lets narrow it down:
If a list has n elements, finding the value at the back of the list would take n times.
This measure of steps/time is called Time Complexity, and for the problem we are doing, it has the worst time complexity of n.
And the best time complexity of 1.
In DSA, we denote it as:
O(n) ← worst time complexity of n ← Big O of n
O(1) ← best time complexity of 1 ← Big O of 1 — also Linear Time complexity
Congrats!!!
You just learned Linear Search and its Time Complexity.
No matter how long the list is, it always takes the maximum length of the list to find any numbers in that list.
- for a list of 5 elements, it would take us a maximum of 5 steps to find an element
- for a list of 10 elements, it would take us a maximum of 10 steps in the solution
- for a list of 20 elements, it would take us a maximum of 20 steps to find a solution
This means that as we increase the length of the list to n,
the worst time will increase to n as well.
If we plot it in the graph, the graph will look like this.
So, whenever you see O(n), you read it as,
As we increase the problem to n, the worst time to complete the problem will be n as well.
So, any algorithm that takes less than O(n) time is good and if it takes more than O(n) then its not good.
We will learn what these are later, but:
O(n²) means that as we increase the list to n, the worst time to complete the problem will be n². It is called having a Quadratic time complexity.
O(log n) means that as we increase the list to n, the worst time to complete the problem will be log n. It is called having a Logarithmic time complexity.
O(2^n) means that as we increase the list to n, the worst time to complete the problem will be 2^n. It is called having an Exponential time complexity. We should avoid having this complexity.
Only O(logn) has a graph in a Good direction among these three graphs. And is considered a good time complexity for large inputs.
In DSA, we often want to achieve a time complexity of O(log n) or less. But less is not easy to achieve, so O(log n) is the standard for now.
Algorithms like Binary Search (already sorted) have a time complexity of O(logn). So, already sorted binary search is considered an efficient search algorithm. We will discuss this in another article.
Here are all of those graphs in a single one.
I hope you learned something from this article. We will discuss more about the complexity of algorithms in future article.
References
GeeksforGeeks. (2024, May 16). What is Logarithmic Time Complexity? A Complete Tutorial. GeeksforGeeks. https://www.geeksforgeeks.org/what-is-logarithmic-time-complexity/
Mathway | Algebra Problem Solver. (n.d.). https://www.mathway.com/Algebra
