- \n
- Asymptotic analysis is the running time of any process or algorithm in mathematical terms.<\/span><\/li>\n
- We can calculate the best, average, and worst-case scenarios for an algorithm by using asymptotic analysis.<\/span><\/li>\n<\/ul>\n
Basics of asymptotic analysis<\/h3>\n
In computer programming, the asymptotic analysis tells us the execution time of an algorithm. The lesser the execution time, the better the performance of an algorithm is.<\/p>\n
For example, let’s assume we have to add an element at the starting of an array. Since an array is a contiguous memory allocation, we cannot add an element at the first position directly. We need to shift each element to the next position and then only we can add elements at the first position. So we need to traverse the whole array once. The greater the array size, the longer the execution time.<\/p>\n
While performing a similar operation on a linked list is comparatively very easy since in a linked list each node is in connection with the next node via a pointer. We can just create a new node and point it to the first node of a linked list. So you can see that adding an element at the first position in a linked list is very much easier as compared to performing a similar operation on an array.<\/p>\n
We similarly compare different data structures and select the best possible data structure for an operation. The less the execution time, the higher the performance.<\/span><\/p>\n
How to find time complexity?<\/h3>\n
Computing the real running time of a process is not feasible. The time taken for the execution of any process is dependent on the size of the input.<\/p>\n
For example, traversing through an array of 5 elements will take less time as compared to traversing through an array of 500 elements. We can observe that time complexity depends on the input size.<\/p>\n
Hence, if the input size is \u2018n\u2019, then f(n) is a function of \u2018n\u2019 denoting the time complexity.<\/strong><\/p>\n
How to calculate f(n) in data structure?<\/h3>\n
Calculating f(n) value for small programs is easy as compared to bigger programs.<\/span><\/p>\n
We usually compare data structures by comparing their f(n)values. We also need to find the growth rate of an algorithm because in some cases there is a possibility that for a smaller input size, one data structure is better than the other but when the input data size is large, it\u2019s vice versa.<\/span><\/p>\n
For example:<\/strong><\/p>\n
Let\u2019s assume a function f(n) = 8n2 <\/sup><\/span>+5n+12.<\/span><\/p>\n
Here n represents the number of instructions executed.<\/span><\/p>\n
If n=1 :\u00a0<\/span><\/p>\n
Percentage of time taken due to 8n<\/span>2<\/span><\/sup> = (<\/span>8\/(<\/span>8+5+12))<\/span>*100 = 32%<\/span><\/p>\n
Percentage of time taken due to 5n = (<\/span>5\/(<\/span>8+5+12))<\/span>*100 = 20%<\/span><\/p>\n
Percentage of time taken due to 12 =<\/span> (12\/(<\/span>8+5+12))<\/span>*100 = 48%<\/span><\/p>\n
In the above example, we can see that most of the time is taken by \u201812\u2019. But based on only one example we cannot conclude time complexity. We have to calculate the growth factor and then observe the situation as we did in the table below.<\/span><\/p>\n
- We can calculate the best, average, and worst-case scenarios for an algorithm by using asymptotic analysis.<\/span><\/li>\n<\/ul>\n
![\"Asymptotic](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Asymptotic-notation.jpg\")
<\/a><\/p>\n