Complexity of an algorithm, Data Structure & Algorithms

Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.                                                                                                                

Ans:

The complexity of the algorithm M is the function f(n) which gives the running time or storage space requirement of the algorithm in terms of the size n of the input data. Frequently, the storage space needed by an algorithm is just a multiple of the data size n. Therefore, the term "complexity" should be referring to the running time of the algorithm.

We find the complexity function f(n) for the certain number of cases. The two cases to which one usually investigates in complexity theory are as follows:-
i. The worst case:-  the maximum value of f(n) for any input possible
ii. The best case:-  the least possible value of f(n)

For example:-

Hear if we take an example of linear search in which an integer Item is to searched or found in an array Data. The complexity if the search algorithm is given by number C of comparisons between Item and Data[k].

Worst case:-

The worst case occurs when the Item is last element in the array Data or is it not there at all. In both of these cases, we get

C(n)=n

In the average case, we presume that the Item is present is the array and is likely to be present in any position in the array. Hence the number of comparisons can be any of the numbers 1, 2, 3........n and each number occurs with probability

p = 1/n.

C(n) = 1. 1/n + 2.1/n + ... + n.1/n

= (n+1) / 2

hence the average number of comparisons needed to locate the Item in to array Data is approximately the same to half the number of elements in the Data list.

Posted Date: 7/10/2012 5:18:56 AM | Location : United States







Related Discussions:- Complexity of an algorithm, Assignment Help, Ask Question on Complexity of an algorithm, Get Answer, Expert's Help, Complexity of an algorithm Discussions

Write discussion on Complexity of an algorithm
Your posts are moderated
Related Questions

(a) Explain the term Group Support System and elaborate on how it can improve groupwork. (b) Briefly explain three advantages of simulation. (c) Explain with the help of a

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Explain CAM software CAD/CAM software has been recognized as an essential tool in the designing and manufacturing of a product due to its ability to depict the designs and tool

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain. (a) 61 52 14 17 40 43 (b) 2 3 50 40 60 43 (c)

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

how to write a function of area of a circle using python

a. In worst case the order of linear search is O (n/2) b. Linear search is more competent than Binary search. c. For Binary search, the array must be sorted in ascending orde