There are two main measures for the efficiency of an algorithm. The complexity of an algorithm is divided into two types:
- Time complexity
- Space complexity
The space complexity of an algorithm describes the amount of memory required during the program execution as the function input. Generally, the space needed.
Space required by an algorithm equals the sum of the following two components.
- A fixed part independent of the particular problem includes instruction space, space for constants, simple variables, and fixed-size structure variables.
- A variable part that includes structured variables whose size depends on the particular problem being solved, dynamically 2000.
Space complexity S(a) of any algorithm a is S(a) = c + v(i), where c is the fixed part, and v(i) is the variable part of the algorithm which depends on an instance characteristic i.
The total time needed to complete the execution of an algorithm is called time complexity. The time complexity depends on all factors that the space complexity depends on. Time requirements can be defined as the numerical function T(num), where T(num) can be measured as the number of steps, provided each step consumes the constant time.
Cases for Complexity of an Algorithm
The major criteria for the complexity of any algorithm are comparing the keys and moving of data, which means the number of times the key is compared, and data is moved.
We take three cases for the complexity of an algorithm.
- Worst-case time complexity
- Average case time complexity
- Best case time complexity
BYJU's Exam Prep Online Classroom Program