Time Complexity and Space Complexity | All you need to know !

Hey Guys!

So in this blog, I would like to discuss about the Time and Space Complexity of an algorithm.

What is a Complexity of an Algorithm??

Complexity , generally means the complication or the difficulty or the complicatedness . But then what does Complexity of an Algorithm means??

Is complexity of an algorithm very complex ?? :( !!

But here it does not refer to the complication or the difficulty of an algorithm, instead Complexity of an Algorithm is a concept in Algorithm Analysis which deals with the execution or running time(number of computer instructions executed per second) of various operations involved.

Suppose an example : ‘X’ is an algorithm and ’n’ be the size of input data provided to algorithm to work upon. So here the time and space implemented by this algorithm ‘X’ are the 2 main factors responsible for efficiency of ‘X’.

So to design a algorithm there are multiple ways but we must always consider the time and space complexity during developing it.

Time Complexity

So, the Time Complexity of a program is not the actual time taken for the program to execute, rather it is the number of times a logical statement gets executed to produced the output. Or in other words, it is the amount of number of operations performed by a program with respect to input size.

Let’s see an example:

main()
{
  int i, n = 5;
  for (i = 1; i <= n; i++) {
  print("Hello");
 } 
}
Output : 
Hello
Hello
Hello
Hello
Hello

So when u run above such command, u will see that compiler has given the above output and along with that it also shows that the code was executed in 1.166 secs.

So is this (1.166 secs) the time complexity??

NO !!

A lot us may assume that this is time complexity but it isn't.

Instead Time-Complexity is dependent on the the number of times the statements get executed. SO in above code, the loop gets executed ‘5’ times, i.e n = 5, i.e ’n’ times , hence complexity is O(n).

So basically there are 3 types in which a time complexity of an algorithm can be represented , these are called Asymptotic Notations :

• Θ Notation (theta)
• Big O Notation
• Ω Notation

Big O Notation

So Big O notation is the most used notation to express the time complexity of an algorithm.

So it defines the upper bound of any algorithm i.e. you algorithm can’t take more time than this time.

In other words, we can say that the big O notation denotes the maximum time taken by an algorithm or the worst-case time complexity of an algorithm.

How to find Time Complexity of a code?

As we did earlier, we calculated the number of times a loop runs in a code and determined the time complexity to be O(n).

Similarly lets try out some more examples:

for (let i = 0; i < n; ++i) 
{
  print(i);
}
for (let j = 0; j < n; ++j) 
{
 print(j);
}

Here there are 2 loops running , so yes loops run 2n times but it is just expressed as O(n) as the value is linear not quadratic, i.e in case of very much larger values, the constant ‘2’ wont affect drastically in the way the ’n’ does, hence the constant ‘2’ is ignored.

Similarly, every program’s time complexity is calculated based on the polynomial expression it forms and thus considering the highest degree of expression(as for higher values, only the highest degree affects).

for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 print(i, j);
 }
}

Here there are 2 loops running but during each iteration in the first loop , there is an inner loop being iterated, hence here the loop will run n² times. Hence the time complexity : O(n²)

for (int i = 1; i <= n; i *= 2) {
    print(i);
}

Now, here in this statement the iterator proceeds exponentially, i.e the iterations get reduced logarithmically. Hence time complexity : O(log n)

Space Complexity

Space Complexity is the total amount of space or memory consumed by an algorithm along with the memory of input values.

So basically,

Space Complexity = Auxiliary space + Space of Input Values.

Here Auxiliary space refers to temporary or extra space used by the algorithm while it is being executed.

The best algorithm/program should have the least space complexity. The lesser the space used, the faster it executes.

Space complexity plays a vital role in algorithmic efficiency. If an algorithm takes some time to execute we can still wait for it to complete, but if a program takes up a lot of memory space, the compiler will not let us run it!

Let’s see an example to calculate Space Complexity:

int main()
{
  int a = 5, b = 5, c;
  c = a + b;
  print(c);
}
Output:
CPU time: 0.00 sec(s), Memory: 1364 Kilobytes(s)
10

In the above program, 3 integer variables are used. The size of the integer data type is 4 bytes which depends on the compiler. So, the total space occupied by the above-given program is 4 * 3 = 12 bytes.

Hence Space Complexity : O(1) or constant

Now let’s see another example:

int main()
{
  int n, i, sum = 0;
  cin>>n;
  int arr[n];
  for(i = 0; i < n; i++)
  {
    cin>>arr[i];
    sum = sum + arr[i];
  }
  cout<<sum;
}
Output:
10

In the above code, array consists of n elements, So space occupied by array is 4*n. Also we have variables like n , i and sum each with 4 bytes size. So the total space consumed by program will be 4*n + 12 bytes. So in this expression the highest order is considered i.e ’n’ , hence Space Complexity : O(n)

So in this way, we can calculate the Time and Space complexities and try to implement efficient Algorithms .

See You in next Blog, Thank You For Your Time !!