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 stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

Determine the types of JAVA Java has two parts... 1. Core language -- variables, arrays, objects o Java Virtual Machine (JVM) runs the core language o Core language is

Define Big Omega notation Big Omega notation (?) : The lower bound for the function 'f' is given by the big omega notation (?). Considering 'g' to be a function from the non-n

A freight train from Melbourne is approaching Sydney, carrying n cars of cargos. The cargos are to be delivered to n different cities in the metropolitan area of Sydney - one car f

What are the structures used in file-system implementation? Several on-disk and in-memory structures are used to execute a file system a. On-disk structure include P

A graph with n vertices will absolutely have a parallel edge or self loop if the total number of edges is greater than n-1

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca