Complexity of an algorithm, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Complexity of an algorithm

Implementation of stack using arrays, A Stack has an ordered list of elemen...

A Stack has an ordered list of elements & an array is also utilized to store ordered list of elements. Therefore, it would be very simple to manage a stack by using an array. Thoug

Randomized algorithm, need an expert to help me with the assignment

need an expert to help me with the assignment

Explain multiplication method, Multiplication Method: The multiplication m...

Multiplication Method: The multiplication method operates in 2 steps. In the 1ststep the key value K is multiplied by a constant A in the range O

Explain worst fit method, Worst Fit method:- In this method the system alw...

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Green computing, In the present scenario of global warming, the computer ha...

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Differentiate between nonpersistent and 1-persistent, Differentiate between...

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist

HUFFMAN CODING, Ask question 1. Indicate whether each of the following prop...

Ask question 1. Indicate whether each of the following properties is true for every Huffman code. a. The codewords of the two least frequent symbols have the same length. b. The

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Lists, In the earlier unit, we have discussed about the arrays. Arrays are ...

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Data type, Q. Define the terms data type and abstract data type. Comment up...

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd