MCA - Design and Analysis of Algorithms - What is Algorithm Analysis and Complexity (#mcanotes)(#ipumca)
ANALYSIS AND COMPLEXITY OF ALGORITHMS
Q1: What do you mean by "Analysis of algorithm"?
Answer: “Analysis of algorithm” is a field in computer science whose overall goal is an understanding of the complexity of algorithms (in terms of time Complexity), also known as execution time & storage (or space complexity) requirement taken by that algorithm.
Suppose M is an algorithm, and suppose n is the size of the input data. Time is measured by counting the number of key operations T(n).
The space is measured by counting the maximum of memory needed by the algorithm S(n).
Q2: What is complexity function? What are its types?
Answer: The complexity of an algorithm M is the function f(n), which give the running time and/or storage space requirement of the algorithm in terms of the size n of the input data.
In general the term “complexity” given anywhere simply refers to the running time of the algorithm.
In general, there are three cases, in general, to find the complexity function f(n):
① Best case: The minimum value of f(n) or any possible input.
② Worst case: The maximum value of f(n) or any possible input
③ Average case: The value of f(n) which is in between maximum and minimum for any possible input. Generally the Average case implies the expected value of f(n).
Q3: Write an algorithm or program function of Linear Search and perform analysis of the linear search algorithm.
Answer: Algorithm: (Linear search)
/* Input: A linear list A with n elements and a searching element .
Output: Finds the location LOC of in the array A (by returning an index )
or return LOC=0 to indicate is not present in A. */
1. [Initialize]: Set k=1 and LOC=0.
2. Repeat step 3 and 4
3. if (x == A[k])
4. {
5. LOC = k;
6. K = K + 1;
7. }
8. if (LOC == 0)
9. printf("x is not present in the given array A");
10. else
11. printf("x is present in array A at location A[LOC]);
12. Exit (end of algorithm)
Analysis of linear search algorithm
The complexity of the search algorithm is given by the number C of comparisons between x and array elements A[K].
Best case: Clearly the best case occurs when x is the first element in the array A.
That is x = A[LOC]. In this case C(n) = 1.
Worst case: Clearly the worst case occurs when x is the last element in the array A or x is not present in given array A (to ensure this we have to search entire array A till last element). In this case, we have: C(n) = n
Average case: Here we assume that searched element x appear array A, and it is equally likely to occur at any position in the array. Here the number of comparisons can be any of numbers
1,2,3,4...,...,n, and each number occurs with the probability p = 1/n then,
C(n) = 1.(1/n) + 2.(1/n) + ... + n.(1/n)
= (1 + 2 + ... + n)(1/n)
= n(n+1)/(2n) = (n+1)/2
It means the average number of comparisons needed to find the location of x is approximately equal to half the number of elements in array A.
It may be noted that the complexity of an algorithm in the average case is much more complicated to analyze than that of worst case. Unless otherwise stated or implied, we always find and write the complexity of an algorithm in the worst case.
