Efficiency of an Algorithm
By BYJU'S Exam Prep
Updated on: September 25th, 2023
In this article, we learn about the two main measures for the efficiency of an algorithm. The two main measures for the efficiency of an algorithm are time complexity and space complexity, but they cannot be compared directly. So, time and space complexity is considered for algorithmic efficiency.
An algorithm must be analyzed to determine the resource usage of the algorithm. An algorithm’s efficiency is referred to as the number of computational resources used by the algorithm. Therefore, the efficiency of an algorithm can be measured based on the usage of different resources. For maximum efficiency of an algorithm, we wish to minimize resource usage.
Download Formulas for GATE Computer Science Engineering – Programming & Data Structures
Table of content
What are the Two Main Measures for the Efficiency of an Algorithm?
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
What are the Two Main Measures for the Competence of an Algorithm?
The two main measures for the competence of an algorithm are also Time complexity and Space complexity.
Download Formulas for GATE Computer Science Engineering – Discrete Mathematics
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 includes structured variables whose size depends on the 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.
Download Formulas for GATE Computer Science Engineering – Algorithms
Time complexity
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
Get complete information about the GATE exam pattern, cut-off, and all those related things on the Byju Exam Prep official youtube channel.