Day 57 - Calculating Time Complexity Of An Algorithm

I recently watched many videos and read one or two articles to understand how to calculate the time complexity of an algorithm but I don't know why this thing is not getting into my head. But I will learn this today by any way possible so here I go.

What is Time Complexity?

First I should know what is time complexity of an algorithm which I think I have already written two time before on other posts but here I will explain it again.

Time Complexity of an algorithm is the estimation of time an algorithm will take to solve a problem when provided with a large input. It is calculated to know how well an algorithm in terms of time will perform when given a large data set as an input to solve some problem.

Time complexity if calculated by caluculating the number of steps the algorithm will take times the time it takes one step to complete. For example a simple for loop that run for n times and prints n times will have the time complexity of O(n). O(n) will be large if the input data set is large and thus will take more time to complete.

for (var i = 0; i < n; i++) {
  console.log(i); // 1 2 3 4 5 6 . . . n
}

That was simple enough to know but how do we calculate the time complexity of other more complex algorithms?

Calculating The Time Complexity

As I wrote above that the steps that an algorithm will take to solve a problem are calculated in order to know its time complexity. I will now try to calculate the time complexities of some simple tasks like loops etc by calculating the steps of the task.

Example 0 - Simple For Loop

As an example above I mentioned that a simple loop will have a time complexity of O(n) as the loop will run n times as shown below.

for (let i = 0; i < n; i++) {
  console.log(i); // Will print n times
}

Technically the loop will run n+1 times but it is the same as n for large numbers like a thousand or a million.

Example 1 - Nested Loops

Now let's calculate the time complexity of the following code which is a loop inside a loop.

for (let i = 0; i < n; i++) {
  // Outer loop runs for n times
  for (let j = 0; j < n; j++) {
    // Inner loop runs for n times
    console.log(`Outer: ${i}, Inner: ${i}`);
  }
}

As both the inner and outer loop runs n times we will say that this process will take n time n steps to complete so it has the time complexity of O(n*n) or O(n^2).

Example 2 - Merge Sort

Now I will try to calculate the time complexity of some more complex algorithm than the previous ones and that is Merge Sort. But first we have to know how merge sort works and that I have explained in Day 54.

Merge Sort have two functions, one is merge and the other is MergeSort itself.

Merge function will take N steps to process because it is looping through each list to merge them. So its function is O(N).

MergeSort function will take LogN steps to return the result becasue on every step it is furthur dividing the lists recusively. So its function becomes O(LogN) Combining them both we get the time complexity of MergeSort which is O(NLogN).

I am sure i have missed some things in the process and still cannot calculate for more comlex algorithms but I think that is enough for today.

zainscizainsci