Calculation of the Comparative Efficiency of Algorithms Using a Single Metric

Abstract

While time complexity and space complexity of an algorithm helps to determine its efficiency when time or space needs to be optimized respectively, they fail to determine the more efficient algorithm when time and space both need to be optimized simultaneously. This resulted in the development of the A1-Score Factor which solve the problem i.e., helps to find the algorithm which optimizes both time and space simultaneously. The following research paper contains the hypothesis, the proof, the theoretical and the graphical implementation of the A1-Score Factor along with the use cases of the same.

Introduction

I. INTRODUCTION

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. The time complexity of an algorithm varies vastly with different inputs of same size. Therefore, usually in case of time complexity, we consider the worst-case scenario, which is the maximum amount of time required for inputs of a given size. The time complexity is generally expressed using the big O notation. For example, O (log n), O(n), O (n log n), O(2n) etc., where n is the size in units of bits needed to rep-resent the input. For any algorithm having O(n) time complexity, the algorithm is said to have linear time. Similarly, O (log n) refers to logarithmic time. An algorithm with time complexity O(nµ) for any µ > 1 is a polynomial time algorithm.

Space complexity, on a similar note, is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input i.e., the memory required by an algorithm until it executes completely. It is also generally asymptotically expressed in big O notation. E.g., O(n) may correspond to linear space complexity while O (log n) will correspond to logarithmic space complexity.

While space complexity of an algorithm may refer to the total space consumed by an algorithm, auxiliary space complexity on the contrary refers to the space other than that consumed by the input. E.g., space complexity of Heap Sort algorithm is O(n) but auxiliary space complexity for the same is O (1) i.e., constant space for any given input.

II. THE PROBLEM

While time and space complexity are a great way for expressing the time it will take for the algorithm to execute or the amount of space it will consume for complete execution, they fail to give us an idea of the comparative efficiency for two algorithms taken into consideration. For example, we know that O(n) is better than O(n2) i.e., linear time is better than quadratic time and O (log n) is better than O(n) i.e., logarithmic time is better than linear time. The case of space complexity is quite similar. Time complexity helps to determine the more efficient algorithm when time needs to be optimized and space complexity helps to determine the more efficient algorithm when space needs to be optimized. But they fail to determine the more efficient algorithm when time and space both need to be optimized. For example, let us consider two algorithms:

Algorithm 1: Time Complexity = O(n), Space Complexity = O (n log n)

Algorithm 2: Time Complexity = O (log n), Space Complexity = O(n2)

For Algorithm 1, the space complexity is better than that of Algorithm 2. But, the time complexity of Algorithm 1 is worse than that of Algorithm 2. So, in a scenario where both the time and the space need to be optimized it would be difficult for us to predict which of the two algorithms mentioned above would provide better overall efficiency.

III. A PROBABLE SOLUTION

A similar problem was encountered in the case of precision and recall in classification problems of unsupervised ma-chine learning. While a high precision and lower recall pro-vided a higher confidence in the True Positive results i.e., low number of False Positive results but came with a trade-off of a large number of False Negative results because of a higher threshold. On the other hand, a high recall and lower precision provided a low number of False Negative results but came with the trade-off of lower confidence in the True Positive results i.e., a large number of False Positive results. Thus, to come up with a good set of precision and recall value for balancing a relatively high accuracy of the True Positive results and a relatively low number of False Negative results, the F-Score or F1-Score was discovered which provided a single number as a metric for measuring the effective-ness of the choice of the precision and recall for the problem statement.

A similar approach could be followed for solving this problem where a single measure could be devised for finding the comparative efficiency of two algorithms taken into con-sideration i.e., which of the two will perform better when both time and space need to be optimized.

IV. INTRODUCTION OF A1-SCORE FACTOR

A1-Score or A-score is a metric developed for solving the above-mentioned problem. It is a function that takes the time complexity and space complexity of the algorithm and returns a number based on an arbitrary value of ‘n’ provided by the user.

VIII. USE CASE SCENARIOS

The A1-Score can be used in use cases which require the determination of a more efficient algorithm in which time and space both time and space have to be optimized simultaneously. While time complexity gives us the more efficient algorithm when time is optimized and space complexity gives us the more efficient algorithm when space is optimized, A1-Score on the contrary gives us the more efficient algorithm which optimizes both time and space simultaneously. Both the theoretical and the graphical implementation of A1-Score can be used as an easy way of knowing the more efficient algorithm.

IX.  ACKNOWLEDGEMENT

Firstly, I would like to thank my parents and relatives for supporting me throughout the journey. Next, I would like to thank all the computer science teachers of Delhi Public School Ruby Park for understanding my potential and helping to increase the same. Finally, I am heavily indebted to the IJRASET review board for reviewing my research paper and selecting it for publishment in the same.

Conclusion

Being faced with a problem of determining the comparative efficiency of two algorithms so as to optimize both time and space simultaneously, the A1-Score was developed by Arya Chakraborty. The A1-Hypothesis states that for two algorithms taken into consideration, the one having the higher value of A1-Score will be more efficient if and only if the product of time and space complexity of the two algorithms are not equal. In the case that the product of the time and space complexity for the two algorithms are same, then the opposite is true i.e., the one having the lower value of the A1-Score will be more efficient. In the A1-Score the product of the time and space complexities is the main indicator for the comparative efficiency of the algorithms. The product is used over the sum of the same as it is better indicator since it will increase more with time and the difference between the product of time and space complexities of the two algorithms will increase over time providing a clear view of the same. In the case where the products are equal, the sum of the time and space complexities is considered and the more efficient algorithm is determined from there.

References

[1] Maharanjan Pradhan and U Dinesh Kumar, “Machine Learning using Python” [2] U Dinesh Kumar, “The Science of Data Driven Decision Making” [3] Eric Siegel, “Predictive Analysis” [4] Time and Space Complexity, https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/, last accessed on 20.04.2023 [5] Time Complexity, https://en.wikipedia.org/wiki/Time_complexity/, last accessed on 20.04.2023 [6] Space Complexity, https://en.wikipedia.org/wiki/Space_complexity/, last accessed on 20.04.2023 [7] Space Complexity in Data Structures, https://www.scaler.com/topics/data-structures/space-complexity-in-data-structure/, last accessed on 20.04.2023 [8] Auxiliary Space Complexity, https://www.geeksforgeeks.org/g-fact-86, last accessed on 20.04.2023

Copyright

Copyright © 2023 Arya Chakraborty. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.