Big-O Time Complexity Analysis Of Algorithm

Time complexity describes the amount of time taken by the computer to run a code by counting the number of operations performed in an algorithm. Algorithms with optimistic logic tend to have less time complexity. Usually, the time complexity is computed theoretically or mathematically. Big O notation describes the worst-case time complexity of the algorithm using algebraic terms. This work calculate the Big O time complexity using two methods: brute force approach and machine learning approach. The Machine learning Approach determines the algorithm's time complexity more rapidly and without executing the code. Lexer is used to extract features from source code in machine learning approach. It is outlined that significant improvement can be achieved in the machine learning approach by giving importance to some known features and increasing dataset size. These two methods are benchmarked on the bubble sort algorithm. Experimental results show that the machine learning approach speeds up time complexity estimate by a factor of up to 97.51% compared to the brute force approach..

I. Introduction

For comparing the performance of different algorithms and to choose the best one to solve a particular problem, we mostly consider time and space as an important factor. The space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input, similarly, time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input[1]. code optimization and selection of algorithms are major advantages of knowing the time complexity of code. Time complexity is not the execution/running time of code. Many factors like hardware, operating system, and processors make an impact on the execution/running time of a given code. Execution/running time of source code is machine-dependent.We try to avoid execution/running time of source code as a measure in the analysis of code. Whereas time complexity is not dependent on execution/running time but it is a theoretical and mathematical concept i.e. in time complexity, amount of seconds required to execute a code doesn't reflect timing performance of code. As amount of time taken to run a code is hardware dependent,we required a mathematical equation which will denote time complexity of program as function of its input. Time complexity is a function of input, it quantifies the total time taken to process an algorithm which is taken as a function of the input. In this paper, we are considering Big O complexity which is worstcase complexity, i.e. for the given input, it is the maximum time taken to process it. So using Big-O complexity we are analysing the efficiency of an algorithm as a function that maps the input size of code to several steps required to execute code in the worst case. If an algorithm has a Time Complexity Big-O of O()whichmeans for N number of input data, number of steps required. Note here that, Number of steps will not be exactly equal to but we consider only dominant terms. Therefore O(N⁴+ N) is equal to ()). Considering below example, $$\begin{gather*} \mathbf{for}(\mathbf{inti=0; i} < \mathbf{n; i++})\\ \{\mathbf{System.out.println}({}^{\prime\prime}\mathbf{Time}{}^{\prime\prime});\} \end{gather*}$$