Space Complexity and Time Complexity

A solution or program for a problem requires some memory for variables, execution of the program, and many more. So, the amount of space required for an algorithm to be executed completely is referred to as space complexity.

Similarly, time complexity refers to the time taken by an algorithm to be executed.However, time complexity or space complexity does not completely refer to the time taken or space taken to execute a program. There are several factors that are taken into consideration while calculating the complexities. 

These factors can be the programming language used, the processing power, operating software, the compiler etc.

Also, a given problem can have many solutions where each solution has its own space complexity, computational power, time complexity and other metrics. Out of all the solutions that we have, it is always better to choose the ones with least complexity.

Space complexity:

Space complexity is a combination of auxiliary space and input space. Where auxiliary space is the extra space or buffer space that will be used by an algorithm during execution. Also, we know that space complexity is all about memory. Below are a few points on how the memory is used during execution.

• Instruction space: the compiled version of instructions are stored in memory. This memory is called instruction space.
• Environmental stack: We use environmental stacks in cases where a function is called inside another function. 

For example, a function cat() is called inside the function animals().

Then the variables of function animals() will be stored temporarily in a system stack when function cat() is being executed inside the function animals().

• Data Space: The variables and constants that we use in the algorithm will also require some space which is referred to as data space.

In most of the cases, we neglect environmental stack and instruction space. Whereas, data space is always considered.

How to calculate space complexity?

To calculate the space complexity we need to have an idea about the value of the memory of each data type. This value will vary from one operating system to another. However, the method used to calculate the space complexity remains the same.

Let’s have a look into a few examples to understand how to calculate the space complexity.

Example 1:

{
    int a,b,c,sum;
    sum = a + b + c;
    return(sum);
}

Here, in this example, we have 4 variables which are a, b, c, and sum. All these variables are of type int hence, each of them require 4 bytes of memory.

Total requirement of memory would be : ((4*4)+4) => 20 bytes.

Here, we have considered 4 additional bytes of memory which is for the return value. Also, for this example as the space requirement is fixed it is known as constant space complexity.

Example 2:

// n is the size of array arr[]
int sum(int arr[], int n)
{
int k, i = 0;
for(k = 0; k < n; k++)
{
    i  = i + arr[k];
}
return(i);
}

In this example, we have 3 variables i, k, n each of which will be assigned 4 bytes of memory. Also, for the return value 4 bytes of memory will be assigned. Here, we also have an array of size n, hence the memory required for that would be (4*n).

Hence the total memory requirement would be : (4n+12)

This value will vary based on the value of n. As the value of n increases the memory would also increase linearly. Therefore it is known as Linear Space Complexity.

Depending on the complexity of the algorithm, the space complexity can range upto quadratic or complex too. We should always try to keep the space complexity as minimum as possible.

Time complexity:

Time complexity is most commonly evaluated by considering the number of elementary steps required to complete the execution of an algorithm. Also, many times we make use of the big O notation which is an asymptotic notation while representing the time complexity of an algorithm. We will be discussing asymptotic notations in the next article.

Now, let’s dive into calculating the time complexity with the help of a few examples.

Constant time complexity:

Example:

Statement – printf(“i2 tutorials”);

In the above example, as it is a single statement the complexity of it would be constant. Its complexity wouldn’t change as it is not dependent on any variable.

Linear time complexity:

Example:

for(i=0; i < N; i++)
{
    statement;
}

Here, the complexity would vary as the number of times the loop iterates would be based on the value of n. Hence, the time complexity would be linear.

Quadratic time complexity:

Example:

for(i=0; i < N; i++) 
{
    for(j=0; j < N;j++)
    { 
    statement;
    }
}

Here, in this example we have a loop inside another loop. In such a case, the complexity would be proportional to n square. Hence, it would be of type quadratic and therefore the complexity is quadratic complexity.

Logarithmic time complexity:

Example:

while(low <= high) 
{
    mid = (low + high) / 2;
    if (target < list[mid])
        high = mid - 1;
    else if (target > list[mid])
        low = mid + 1;
    else break;
}

In this example, we are working on dividing a set of numbers into two parts. Which means that the complexity would be proportional to the number of times n can be divided by 2, which is a logarithmic value. Hence we have a logarithmic time complexity.

We’ve reached the end of the article, and as mentioned earlier do read the next article on asymptotic notations to have a clear idea about the asymptotic notations which will be used while calculating the time complexity.