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
In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

What do you understand by tree traversal? The algorithm walks by the tree data structure and performs some computation at everynode in the tree. This process of walking by the

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.