Complexity of an Algorithm
Algorithm is a step by step instructions for solving any problem, and there can be an unlimited number of solutions to every problem; however, while solving any problem we need to compare the efficiency of all possible solutions to the same problem. That efficiency is in the terms of amount of time and/or space required by an algorithm for an input of a given size (n) and is known as complexity. Lets look at an example to understand the concept of complexity more clearly:
Suppose we want to find the square of a number, and we don’t remember the formula (n*n).
- One solution to this problem is running a loop for n times, starting with the number n and adding n to it each time.
- Other solution is to simply use operator ‘*’
So, we can say that, to solve a particular problem we have multiple solutions. But we will choose second solution as it is better than the first and takes less time to produce result. Based on this analysis, we can infer that the outcome of an algorithm, being executed, depends on different factors. To gauge this, we require to evaluate both Space and Time complexity of an algorithm.
Time Complexity
Time Complexity
The amount of time taken by an algorithm to run as a function is known as time complexity. It measures the time taken to execute each statement of code in an algorithm. It is calculated by counting the number of basic steps taken by any algorithm to complete execution.
Time Complexity Example
In the above figure in CODE 1, the loop will run n times in the initial solution, therefore the time complexity will be at least n, and as the value of n increases, the time consumed will likewise rise. The time complexity of the CODE 2, on the other hand, is constant as it will never be affected by the value of n and will always provide the same result in one step.
Notations of Time Complexity
The three concepts below, known as Asymptotic Notations, can be used to indicate time-complexity:
- Big – O (Big Oh): It is the total amount of time an algorithm takes for all input values. It depicts an algorithm’s worst-case time complexity.
- Big – Ω (Omega): It gives the minimum time required by an algorithm for all input values. It is the best case scenario for an algorithm’s time complexity.
- Big – Θ (Theta): It specifies the average bound of an algorithm and represents the average case of an algorithm’s time complexity.
Most Commonly used notation is the big O notation because it will provide us with an upper bound on the execution time, i.e., the execution time for the worst-case inputs. Worst case complexity is the maximum amount of time required for inputs of a given size.
Space Complexity
The overall amount of memory space utilized by an algorithm/program, including the space of input values for execution, is referred to as space complexity. So, to find the space-complexity, just calculate the space taken by the variables in an algorithm/program. We can say that:
Space Complexity = Auxiliary space + Space use by input values
Space Complexity
Auxiliary space is the extra space or temporary space used by an algorithm. So, remember that the lesser the space used, the faster it executes. It means that the best algorithm will have least space complexity.
Need of Space Complexity
As we discussed earlier, time complexity and space complexity plays a vital role in the efficiency of an algorithm. If an algorithm takes a long time to execute, we can wait to receive the required result, but if a program uses a lot of memory, the compiler will refuse to run it. During execution, an algorithm consumes memory for three reasons:
- Instruction Space: To save the compiled instructions.
- Environmental Stack: When an algorithm is called inside another algorithm, the current variables are pushed on stack. They wait for the next execution before calling the internal algorithm.
- Data Space: Space used by the variables and constants.
However, when calculating the Space Complexity of any algorithm, typically, Data Space is only considered and ignore Instruction Space and Environmental Stack.
Calculation of Space Complexity
Value of memory used by different types of datatype variables is used for calculating space complexity. This value varies for different operating systems, but method remains the same. For example, we have to calculate the space complexity of following code:
{
int z = a + b + c;
return(z);
}
Here, in the code above, ‘a’, ‘b’, ‘c’ and ‘z’ are integer types, so each will take 4 bytes. So, the memory required will be ‘4*4’, i.e., 16 In addition to this memory, while returning value, ‘z’ will take 4 bytes. Therefore, the total memory requirement will be ’16+4′, i.e., 20 bytes. This is the space complexity of the above-given problem