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

Ask an Expert

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

Write your message here..

Related Questions

Row major representation, Row Major Representation In memory the primar... Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

Explain b tree (binary tree), B Tree Unlike a binary-tree, every node o... B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Preorder traversal of a binary tree, Preorder traversal of a binary tree ... Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

Double linked list, In a doubly linked list, also called as 2 way list, eac... In a doubly linked list, also called as 2 way list, each node is divided into 3 parts. The first part is called previous pointer field. It contains the address of the preceding

Search engines - applications of linear and binary search, Search engines e... Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Degree of node, Q. The degree of a node is defined as the number of childre... Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Explain the question, Merging 4 sorted files having 50, 10, 25 and 15 recor... Merging 4 sorted files having 50, 10, 25 and 15 records will take time

Cohen sutherland algorithm, Using the cohen sutherland. Algorithm. Find the... Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

First class Abstract data type , 3. A function to convert a complex number ... 3. A function to convert a complex number in algebraic form to a complex number in phasor form

Define order of growth, Define order of growth The  efficiency  analysi... Define order of growth The  efficiency  analysis  framework  concentrates   on  the  order  of  growth  of  an  algorithm's   basic operation count as the principal indicator o