The complexity of an algorithm is a concept which deals with calculating the amount time and space taken by a program or code to process as according to a given input.

What is Complexity in Data Structure?

Algorithm complexity: Complexity of the algorithm is the rough approximation of the number of steps necessary to execute an algorithm. It is a way to find the efficiency and performance of an algorithm.
There are three types of complexity in Data structure could be considered when analyzing the algorithm complexity in Data structure. These are Worst case complexity, Best-case complexity, Average-case complexity.

Types of algorithm complexity

There are two types of algorithm complexity in Data Structure which are as follow:

1. Time complexity
2. Space complexity

Space Complexity:

Space Complexity is a very important concept in the types of complexity which deals with memory calculations.

What is space Complexity? : The amount of memory required to execute the program is space complexity. It is total memory needed to run to completion of the algorithm. To calculate space complexity we consider memory needed by each instruction and variables used in the program.

Space Complexity example

Let’s try to find space complexity.
Suppose we are adding two integer values. For this assume following two algorithms

Algorithm 1:
Input A
Input B
Set C=A+B
Write Sum is = C
Exit
For algorithm 1 Space required for 3 variable A, B, and C = 6 byte

Algorithm 2:
Input A
Input B
Write Sum is = A+B
Exit
For algorithm 2 Space required for 2 variable A and B = 4 byte
In the above two algorithms, both will produce the same results but the space needed for both algorithm are different because the first algorithm has more instructions than the second one. So which one you will use? Obviously the second algorithm as it takes less space than the first algorithm.

How to calculate space complexity?

For an algorithm, the memory may be used for variables, instructions, and execution.
The space complexity depends on two components: Fixed part and Variable part
Where a fixed part is space for instructions such as variables, constants, etc. and Variable part is space which dynamic which changes according to instructions such as input and output data.

Syntax to calculate space complexity

Space complexity = fixed part + variable part

Time Complexity:

What is Time Complexity? : The amount of time required to execute the program is Time complexity. It is the total time needed to run to completion of the algorithm. To find time complexity we consider both compilation time and run time of an algorithm. The compilation time is the amount of time requiring compiling the code. The compilation time depends on a compiler which differs from compiler to compiler. Compilation time is not controlled by the programmer. So we ignore compilation time and focus on run time. Run time is the amount of time required to execute each instruction in the program. We measure run time on the basis of instruction in code.

Time Complexity example

Let’s try to find time complexity.
Suppose we are adding two integer values. For this assume following two algorithms
Algorithm 1:
Input A
Input B
Set C=A+B
Write Sum is = C
Exit
Algorithm 2:
Input A
Input B
Write Sum is = A+B
Exit
Suppose one instruction requires 1 second to execute than
For algorithm 1 Time require to execute 4 instruction is = 4 seconds
For algorithm 2 Time require to execute 3 instruction is = 3 seconds
In the above two algorithms, both will produce the same results but the time needed for both algorithm is different because the first algorithm has more instructions than the second one. So which one you will use? Obviously the second algorithm as it takes less time than the first algorithm.

Space and time complexity table

Complexity in Data Structure
The complexity of algorithms in Data Structure

The given table Shows the space complexity and Time Complexity of algorithms in Data structure.

Write A Comment