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
Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Q.1 Compare two functions n 2 and 2 n for various values of n. Determine when second becomes larger than first. Q.2 Why do we use asymptotic notation in the study of algorit

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

write a program that find,search&replace a text string

A binary tree of depth "d" is an almost complete binary tree if  A) Every leaf in the tree is either at level "d" or at level "d-1"  B)  For any node "n" in the tree with a

since the gregorian calendar was introduced in 1752,a leap year occurs every 4 years.you are to write a pseudo code to find out whether a year is a leap year.your progrm should dis

Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s