One of the most important concepts in software development is analysing the time complexity of an algorithm. In technical interviews, you'd often find interviewers asking, "What's the time complexity of this algorithm?" or "Can you improve the time complexity?" If you've no idea what time complexity means or what the fuss about Big O is all about, stick till the end to find out!
What is Time Complexity?
Time complexity is the time taken by an algorithm as a function of the length of the input. In short, it tells the running time or performance of a program as the size of the input is varied.
Why do we need to understand Time Complexity?
Time complexity helps us to determines the scalability of an algorithm. Suppose, you're at a party and you want to use an Instagram filter to capture the joyous occasion. Alas, the filter takes years to load. Your smiles turn into a frown as your mood gets ruined. So much for a party, huh?
As a developer, it is necessary to understand which is the most efficient and optimised method to use in an application.
How to compare the time complexity of an algorithm?
Let us take an example to understand this problem. Ali and Jack were given a task to write a program to find the sum of n numbers. Jack is a very hardworking guy who has mastered the fundamentals of a programming language. He doesn't pay attention to anything except programming. Here's how he coded the program:
<span class="hljs-type">int</span> n=<span class="hljs-number">10</span>, sum = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i=<span class="hljs-number">1</span>; i<=n; i++)
{
sum = sum + i;
}
<span class="hljs-keyword">System</span>.<span class="hljs-keyword">out</span>.println(sum);
Ali was smart. He focused on every subject in school and solved problems in a jiffy. When Ali was granted the same problem, he chuckled and used Mathematics to his aid. Here's how Ali built his program:
<span class="hljs-type">int</span> n=<span class="hljs-number">10</span>;
<span class="hljs-keyword">System</span>.<span class="hljs-keyword">out</span>.println((n*(n+<span class="hljs-number">1</span>))/<span class="hljs-number">2</span>);
As you see from the above scenario, Ali was much more efficient as he avoided the shackles of using a loop to calculate his answer. If the size of the input increases, Jack's program will start to freeze and eventually int will overflow to present the wrong answer. Ali's magical line saves time and gives the right answer even for larger numbers.
What is Big O?
View Website
View Website
View Website
Image Source: BigOCheatSheet
Based on logic, we have understood time complexity and its comparison but we need something very distinct to compare the performance of different algorithms. If we start comparing the different type of sorting techniques by logic, it would get real tedious for our brain to execute the complexity of our problem. To optimise this, there's a superhero called the Big O.
As per Wikipedia, Big O or asymptotic notation is a mathematical function that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
Big O basically tells us the time complexity in mathematical terms which can be easily compared. Our superhero Big O comes in different forms and sizes. I'll introduce you to them, right away!
Understanding O(1)
O(n) stands for constant time complexity. O(1) represents that no matter the size of the input, it takes the same amount of time to execute. For example,
<span class="hljs-attribute">int</span> b = {<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>}
<span class="hljs-attribute">System</span>.out.println(b[<span class="hljs-number">0</span>]);
No matter the length of the array, the program will require one unit, constant time.
Understanding O(n)
O(n) stands for linear time complexity. Linear represents the time takes by the algorithm is directly proportional to the size of the input. One of the most famous examples is the Linear Search algorithm. In linear search, we iterate over each element of the loop until we find a match. In the best-case scenario, the element could be present in the first position itself, thus effectively reducing the time complexity to O(1) as seen above. On the other hand, if the element is present at the end of the array or not at all, the loop has to iterate over all the elements in the array. Hence, the time complexity increases to O(n).
<span class="hljs-string">int</span> <span class="hljs-string">a</span> <span class="hljs-string">=</span> <span class="hljs-number">0</span><span class="hljs-string">,</span> <span class="hljs-string">n[]</span> <span class="hljs-string">=</span> {<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>}<span class="hljs-string">;</span>
<span class="hljs-string">for(int</span> <span class="hljs-string">i</span> <span class="hljs-string">=</span> <span class="hljs-number">0</span><span class="hljs-string">;</span> <span class="hljs-string">i</span> <span class="hljs-string"><n.length;</span> <span class="hljs-string">i++)</span>
{
<span class="hljs-string">if(n</span>[<span class="hljs-string">i</span>]<span class="hljs-string">==a)</span>
{
<span class="hljs-string">System.out.println("Found");</span>
<span class="hljs-string">break;</span>
}
}
Note: If there are two for loops in a program, the effective time complexity is still considered as O(n) and not O(2n). We typically ignore the constants in front of the variables in such cases, because they both still represent a linear function.
Understanding O(logn)
O(logn) also known as logarithmic time complexity denotes the time taken by the program to execute is proportional to the logarithm of the size of the input. The most famous example of this is the Binary Search algorithm. Let's suppose the worst-case scenario in the Binary search algorithm. We keep on halving our search array until we find the element or realise it is not present. In an array of 8 elements it will take maximum of 3 iterations(log28) to execute. If there are 1 million elements, it'll take just 19 iterations. This makes Binary Search so much more powerful than Linear Search.
<span class="hljs-attribute">int</span> arr[] = {<span class="hljs-number">10</span>,<span class="hljs-number">20</span>,<span class="hljs-number">30</span>,<span class="hljs-number">40</span>,<span class="hljs-number">50</span>};
<span class="hljs-attribute">int</span> l = <span class="hljs-number">0</span>, r = arr.length - <span class="hljs-number">1</span>;
<span class="hljs-attribute">while</span> (l <= r) {
<span class="hljs-attribute">int</span> m = l + (r - l) / <span class="hljs-number">2</span>;
<span class="hljs-attribute">if</span> (arr[m] == x)
<span class="hljs-attribute">return</span> m;
<span class="hljs-attribute">if</span> (arr[m] < x)
<span class="hljs-attribute">l</span> = m + <span class="hljs-number">1</span>;
<span class="hljs-attribute">else</span>
<span class="hljs-attribute">r</span> = m - <span class="hljs-number">1</span>;
Understanding O(n2)
O(n2) is also known as Quadratic time complexity. It represents that input is proportional to the square of the size of the input. It is most commonly seen in Bubble sort, Insertion sort and Patterns. Nested loops are an easy way to identify the O(n2) complexity.
As the number of nested loops increases so does the power.
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i<=<span class="hljs-number">5</span>; i++)
{
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> j = <span class="hljs-number">1</span>; j<=i; j++)
{
<span class="hljs-keyword">System</span>.<span class="hljs-keyword">out</span>.print(j);
}
<span class="hljs-keyword">System</span>.<span class="hljs-keyword">out</span>.println();
}
Note: If there are instances of multiple nested loops of different orders only the highest power will contribute to time complexity. For example, if T(n) = 3n3 + 2n2+n. The time complexity will be Cubic, O(n3).
Understanding O(2n)
O(2n) represents the exponential function. It is opposite to the logarithmic function. This mostly occurs in the case of Recursive functions, like recursive calculation of Fibonacci numbers. Another famous example of this complexity is the Hanoi Tower Problem.
<span class="hljs-keyword">void</span> solve_hanoi(<span class="hljs-keyword">int</span> N, <span class="hljs-keyword">string</span> from_peg, <span class="hljs-keyword">string</span> to_peg, <span class="hljs-keyword">string</span> spare_peg)
{
<span class="hljs-keyword">if</span> (N<<span class="hljs-number">1</span>) {
<span class="hljs-keyword">return</span>;
}
<span class="hljs-keyword">if</span> (N><span class="hljs-number">1</span>) {
solve_hanoi(N<span class="hljs-number">-1</span>, from_peg, spare_peg, to_peg);
}
<span class="hljs-keyword">print</span> <span class="hljs-string">"move from "</span> + from_peg + <span class="hljs-string">" to "</span> + to_peg;
<span class="hljs-keyword">if</span> (N><span class="hljs-number">1</span>) {
solve_hanoi(N<span class="hljs-number">-1</span>, spare_peg, to_peg, from_peg);
}
}
Program Source: Stack Overflow
Understanding O(n!)
O(n!) represents that the time complexity is the function of n factorial. This is the costliest it can get. One of the most classic examples is the Travelling Salesman Problem. Another example of O(n!) is given below:
<span class="hljs-keyword">const</span> nFacRuntimeFunc = <span class="hljs-function">(<span class="hljs-params">n</span>) =></span> {
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i=<span class="hljs-number">0</span>; i<n; i++) {
nFacRuntimeFunc(n<span class="hljs-number">-1</span>);
}
}
You should at all costs avoid the O(n!) complexity.
Let's Recap:
- O(1) - Constant time complexity (Best🎯)
- O(n) - Linear time complexity
- O(log n) - Logarithmic time complexity
- O(n2) - Quadratic time complexity
- O(2n) - Exponential time complexity
- O(n!) - Factorial time complexity (Worst😭)
Valuable Resource: Big O Cheatsheet
Our superhero deserves a website of his own. I stumbled upon this website called the BigOCheatSheet.com made by Eric. It contains an amazing comparison of the time complexity for different data structures and array sorting elements.
In today's world, people are learning various frameworks, libraries & technologies without learning time complexity or Data Structures & Algorithms(DSA). If you ask any developer working in the top MNC's, they'll advise you to master the fundamentals and learn DSA as it greatly helps in problem-solving and writing efficient code. With that said, I hope our superhero continues to be our guardian angel forever. Cheers🍻
Comments (1)