Twitter Facebook Delicious Digg Stumbleupon Favorites More

Thursday, 12 July 2018

MCA - Design and Analysis of Algorithms - What is Algorithm Analysis and Complexity (#mcanotes)(#ipumca)

ANALYSIS AND COMPLEXITY OF ALGORITHMS

MCA - Design and Analysis of Algorithms - What is Algorithm Analysis and Complexity (#mcanotes)(#ipumca)


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.


Share:

0 comments:

Post a Comment

BCE-Hacks Notes

BCE-Hacks Notes
Chemical Engineering Notes

Maths Resources

Maths Resources
Maths Resources

Buy Books

Buy Books
Buy Books

Geography Quiz

Geography Quiz
Geography Quiz

NodeJS Tutorial

NodeJS Tutorial
Developer-Bytes

History MCQs

History MCQs
History Quiz For Competitive exams

Categories

Popular Posts

GooglePlus

Recent Posts

Unordered List

Express Print Zone

Eduvictors Quizzes

Online Quizzes, Study notes for CBSE Class 6 - 12

Text Widget

Compete4Exams

Study notes for Competitive Exams

Developer Bytes

Developer Bytes
Developer Bytes
Powered by Blogger.

Blogger Tutorials

Blogger Templates

Sample Text

Copyright © IP University Musings BCA, MCA, BBA, MBA, BTech Question Papers and Study Notes | Powered by Blogger
Design by SimpleWpThemes | Blogger Theme by NewBloggerThemes.com