{"id":81060,"date":"2021-06-17T09:00:51","date_gmt":"2021-06-17T03:30:51","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=81060"},"modified":"2021-06-17T09:00:51","modified_gmt":"2021-06-17T03:30:51","slug":"data-structures-asymptotic-analysis","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/data-structures-asymptotic-analysis\/","title":{"rendered":"Data Structures Asymptotic Analysis"},"content":{"rendered":"

In this article, we are going to learn about the concept of asymptotic analysis and various asymptotic notations used for the analysis of any algorithm.<\/p>\n

Defining asymptotic analysis<\/h3>\n

Whenever we write an algorithm for a particular computational problem, we design the algorithm in such a way that it gives the best results in terms of running time as well as memory used.<\/p>\n

While checking the running time for any algorithm, we want three things:<\/p>\n

1. The algorithm should be machine-independent.<\/p>\n

2. It should work on all possible inputs.<\/p>\n

3. It should be general and not programming language-specific.<\/p>\n

However, we never do accurate analysis, rather we do approximate analysis. We are interested in the increase in the running time with the increase in the input size. Thus, we are only interested in the \u2018growth of the function\u2019, which we can measure\/analyse through asymptotic analysis.<\/p>\n

1. Asymptotic analysis is a general methodology to compare or to find the efficiency of any algorithm.<\/p>\n

2. We measure the efficiency in terms of the growth of the function. The growth of any function depends on how much the running time is increasing with the increase in the size of the input.<\/p>\n

Assumptions for Asymptotic Analysis<\/h3>\n

Asymptotic analysis is based upon certain assumptions such as:<\/p>\n

Let Rt be the running time of an algorithm, N be the input size. Then,<\/p>\n

1. Rt \u2265 0 and N\u22650 i.e. both running time and input size should be positive numbers.<\/p>\n

2. The input size is very large while analyzing any algorithm through asymptotic analysis i.e. N\u2192\u221e<\/p>\n

3. The analysis is both hardware independent and software independent.<\/p>\n

4. For better understanding, we do a high-level representation of the algorithm i.e. pseudo-code or English like instructions.<\/p>\n

5. We focus on primitive operations i.e. those operations which are independent of software such as assignment, comparison, arithmetic operations, etc in terms of input size.<\/p>\n

Example:<\/strong><\/p>\n

Let us try to get a brief idea behind the concept of asymptotic analysis with the help of an example.<\/p>\n

1. Suppose we wish to calculate the value of 1 + 2 + 3+ 4+ —— + n<\/p>\n

2. There could be two possible ways to do that.<\/p>\n

3. One of the ways is to write the formula directly as shown:<\/p>\n

int n, sum=0;\nsum = (n * (n+1))\/2;<\/pre>\n
4. Another way is iteratively finding the sum as shown:<\/p>\n
int n, sum=0;\n for(i=1; i<=n; i++){\n     sum = sum + i;\n }\n<\/pre>\n
5. In the first method, where we are using the direct formula, every time the number of steps is the same because, for whatever value of n, the formula will run in a single step.<\/p>\n
6. Thus, we can say that method 1, where we are using the formula to find the sum, is taking constant time because it is completed in a constant number of steps.<\/p>\n
7. However, in the 2nd method, the number of steps executed by the program will depend on the value of n because for loop is running n times.<\/p>\n
8. This is why the number of steps in the 2nd method is not constant but linearly dependent on n.<\/p>\n
9. From here, we can conclude that the computation time taken by the second method is more than the first method.
\nThis is the basis of our analysis.<\/p>\n
How to find the time complexity?<\/h3>\n
1. It is not practically feasible to sit and calculate the time taken by an algorithm to run on a system.<\/p>\n
2. However, we know that the running time of an algorithm depends on the size of the input. So, we can use this input size to analyse the time taken by an algorithm.<\/p>\n
3. Let us again take the above example of finding the sum of first n natural numbers iteratively.<\/p>\n
int n, sum=0;\n    for(i=1; i<=n; i++){\n        sum = sum + i;\n    }\n<\/pre>\n
4. In this code, if the value of n is 10, the algorithm will take 10 units of time.<\/p>\n
5. But for the same code, if the value of n is 1000, the algorithm will take 1000 units of time for execution.<\/p>\n
6. Therefore, if the input is n, then the time complexity for any algorithm is a function of n, say T(n).<\/p>\n
How to calculate the value of T(n)<\/h3>\n
1. Let T(n) be a function that denotes the time complexity for an algorithm.<\/p>\n
2. Then, to find the value of T(n), we need to check for various values of n.<\/p>\n
3. Usually, finding the value of T(n) for smaller problems is easy as compared to the larger ones.<\/p>\n
4. For example, suppose a function is T(n) = 3n2<\/sup> +5n + 8<\/p>\n
5. Then for smaller values of n, such as for n=1,2,3,4\u2026.9, the value of T(n) depends on the whole equation.<\/p>\n
6. However, whenever we do asymptotic analysis, we always consider n to be very large (as described in the assumptions).<\/p>\n
7. For larger values of n i.e. n\u2192\u221e, the value T(n) depends only on the highest power and hardly depends upon other values in the equation.<\/p>\n
8. In the above example, for higher values of n, T(n) will come out to be T(n) = 3n2.<\/p>\n
9. Usually, we discard the value of constant, which is 3 here.<\/p>\n
10. So we can conclude that the value of T(n)=3n2 +5n + 8 is of the order of n2<\/p>\n
Usually, there are three different categories depending on the time taken by an algorithm:<\/p>\n
1. Worst case<\/h4>\n
It describes the scenario in which the algorithm takes the highest amount of time.<\/p>\n
2. Best case<\/h4>\n
It describes the case in which the running time of the algorithm is minimum.<\/p>\n
3. Average case<\/h4>\n
It lies between the best case and worst case. Precisely, it takes the average time that an algorithm will take to execute.<\/p>\n
Asymptotic Notations<\/h3>\n
\"commonly<\/a><\/p>\n
The three most commonly used notations for finding the running time or the time complexity of an algorithm are:<\/p>\n
1. Big Oh notation(O)<\/p>\n
2. Omega notation(\u03a9)<\/p>\n
3. Theta notation(\u03b8)<\/p>\n
1. Big Oh notation(O)<\/h4>\n
a. This notation describes the upper bound of the running time for an algorithm.<\/p>\n
b. Big Oh notation ensures that the function never grows faster than its upper bound.<\/p>\n
c. Thus, it measures the performance of an algorithm by describing the order of growth for a function and by giving the least upper bound for that function.<\/p>\n
d. Big Oh measures the worst-case time complexity for the given algorithm i.e., it measures the longest time an algorithm can execute.<\/p>\n
Computing O(n)<\/h5>\n
a. Let there be two functions- f(n) and g(n) defined for positive integers as shown:<\/p>\n
\"Big<\/a><\/p>\n
b. Then f(n) = O(g(n)) as growth of g(n) is faster than that of f(n).<\/p>\n
c. f(n) = O(g(n)) is read as f(n) is equal to Big Oh of g(n).<\/p>\n
d. Mathematically, we can say that f(n) \u2264 c.g(n) for constants c and n0 where c>0 and n>n0.<\/p>\n
e. This implies that the function g(n) is an upper bound on the function f(n) i.e. f(n) cannot grow faster than g(n).<\/p>\n
Let us try to understand this concept with the help of an example:<\/p>\n
For Example:<\/strong><\/p>\n
1. Let f(n) = 3n+2 and g(n) = n. We need to check whether f(n) = O(g(n)) or not.<\/p>\n
2. For f(n) to be equal to O(g(n)), both the functions f(n) and g(n) must satisfy the following condition: f(n) \u2264 c.g(n).<\/p>\n
3. To check if the condition holds, replace f(n) by 3n+2 and g(n) by n i.e. 3n+2 <= c.n<\/p>\n
4. Let c=7 and n=1, then 3(1)+2 <= 7*1 \u21d2 5<=7 which is true.<\/p>\n
Thus, f(n) <= c.g(n) is true for n=1.<\/p>\n
5. For n=2,
\n3(2)+2 <= 7*2 \u21d2 8 <= 14 which is again true.<\/p>\n
6. Therefore, f(n) <=c.g(n) is true for n=2 as well.<\/p>\n
7. From here, we can conclude that f(n) <= c.g(n) holds for all values of n, given that c=7.<\/p>\n
8. Thus, we can say that the above equation always holds for some constant c and some constant n0.<\/p>\n
9. So, f(n) is equal to Big Oh of g(n) i.e. f(n) = O(g(n)) or we can say that c.g(n) is an upper bound on function f(n).<\/p>\n
\"<\/a><\/p>\n
Big Oh notation always gives the worst-case time complexity for a function or algorithm as it is based on comparison with the upper bound of a function.<\/p>\n
2. Omega notation(\u03a9)<\/h4>\n
1. It is the opposite of Big-Oh notation.<\/p>\n
2. Omega notation always describes the best-case scenario for a particular algorithm.<\/p>\n
3. Omega represents the lower bound of running time for an algorithm.<\/p>\n
4. It will measure the least amount of time that an algorithm can take for its execution in the best case.<\/p>\n
Computing omega:<\/h5>\n
1. Let f(n) and g(n) be two functions defined on a set of natural numbers.<\/p>\n
2. Then, f(n) = \u03a9(g(n)) only if the growth of f(n) is faster than the growth of g(n).<\/p>\n
3. Mathematically, its equation will be f(n) \u2265 c.g(n) where c and n0 are constants such that c>0 and n>n0.<\/p>\n
Let us understand this notation with the help of an example:<\/p>\n
1. Let f(n) = 2n+3, g(n) = n, we need to find whether f(n)= \u03a9 (g(n)) or not.<\/p>\n
2. For f(n) to be equal to the omega of g(n), it must satisfy the condition: f(n)\u2265 c.g(n)<\/p>\n
3. Replace f(n) by 2n+3 and g(n) by n 2n+3 \u2265 c*n<\/p>\n
4. Let c=1 i.e. value of constant c=1.<\/p>\n
5. For n=1,
\n2(1) + 3 \u2265 1(1) .\u21d2 5 \u2265 1 which is true.<\/p>\n
6. Similarly, for n=2,
\n2(2)+3 \u2265 1(2) \u21d2 7 \u2265 2 which is again true.<\/p>\n
7. If we check for further values, the equation holds for every value of n given that c=1.<\/p>\n
\"Omega<\/a><\/p>\n
Here, the function g(n) is the lower bound of the function f(n) and thus it gives the running time for the function f(n) in the best possible case.<\/p>\n
3. Theta notation(\u0398)<\/h4>\n
1. While Big Oh gives the worst-case analysis and omega gives the best case analysis, theta lies somewhere in between.<\/p>\n
2. Theta notation gives the average case analysis for a function or algorithm.<\/p>\n
3. In real-world problems, not every time the algorithm will have either the best or worst-case scenario.<\/p>\n
4. Practically, an algorithm is always performing in some average case i.e. the algorithm keeps on fluctuating.<\/p>\n
Computing Theta<\/h5>\n
1. Let there be two functions: f(n) and g(n) defined on a set of positive integers.<\/p>\n
2. Then, f(n) = \u0398(g(n)) if
\nc1.g(n)\u2264 f(n)\u2264 c2.g(n) where c1, c2 are constants.<\/p>\n
3. In theta notation, two limits bind the function i.e. both the upper limit as well as the lower limit. This is what makes the theta notation return the average case for an algorithm.<\/p>\n
4. Thus, the condition f(n)= \u03b8g(n) becomes true only when c1.g(n) is less than or equal to f(n) and c2.g(n) is greater than or equal to f(n).<\/p>\n
Let us understand the Theta notation with the help of an example:<\/p>\n
1. Let f(n) = 2n+3 and g(n) = n.<\/p>\n
2. Replace f(n) with 2n+3 and g(n) with n in the equation c1.g(n)\u2264 f(n)\u2264 c2.g(n).<\/p>\n
Then the equation will be c1.n \u22642n+3\u2264 c2.n<\/p>\n
3. To ensure that the equation holds, let c1=1 and c2=5.<\/p>\n
4. Thus, for n=1,
\nthe equation will be 1(1) \u2264 2(1)+3 \u2264 5(1) \u21d2 1 \u2264 5 \u2264 5 which is true.<\/p>\n
5. For n=2,
\nThe equation will be 1(2) \u2264 2(2)+3 \u2264 5(2) \u21d2 2 \u2264 7 \u2264 10 which is again true.<\/p>\n
\"Asymptotic<\/a><\/p>\n
6. Hence, we can say that the equation holds for all the values of n given that c1=1 and c2=5.<\/p>\n
7. Therefore, we can say that for the above example, f(n) is equal to \u03b8(g(n)). And it gives average-case complexity for f(n).<\/p>\n
Example:<\/strong><\/p>\n
Let us consider the following example for more understanding:<\/p>\n
Assume we have to reverse the string: \u201cTechVidvan\u201d. The traditional algorithm for it is:<\/p>\n
1: START<\/p>\n
2: Declare two variables str1 and str2.<\/p>\n
3: Initialize the variable str1 with \u201cTechVidvan\u201d<\/p>\n
4: Traverse to the last character of str1<\/p>\n
5: Beginning from the end, take each character from str1 and append it to str2.<\/p>\n
6: Display str2.<\/p>\n
7: END<\/p>\n
In this algorithm, every time we execute step 5, a new string gets created instead of appending to the original string. This is why the complexity of the above algorithm is O(n2).<\/p>\n
However, in JAVA, we don\u2019t need to reallocate the string to str2. In JAVA, the function StringBuffer.reverse() reverses the string without reallocation. Therefore, reversing a string in JAVA takes O(1) time.<\/p>\n
Need for asymptotic analysis<\/h3>\n
In simple words, we need asymptotic analysis to find the best possible algorithm for our problem.<\/p>\n
Let us understand this with the help of an example:<\/p>\n
Suppose we wish to search an element inside an array. There could be multiple ways to do this. Two of the ways are- Linear search and Binary search.<\/p>\n