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

Prims algorithm, how to write prims algorithms? with example

how to write prims algorithms? with example

#, write an algorithm to search a particular node in linked list which retu...

write an algorithm to search a particular node in linked list which returns " FOUND" or "NOT FOUND" as outcome.

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

Small program on Algorithms , Objective The goal of this project is to ext...

Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Limitation of binary search, Limitation of Binary Search: - (i)  The co...

Limitation of Binary Search: - (i)  The complexity of Binary search is O (log2 n). The complexity is similar irrespective of the position of the element, even if it is not pres

Algorithms, characteristics of a good algorithm

characteristics of a good algorithm

Abstract data type-list, It is a useful tool for indicating the logical pro...

It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

Illumination of wire frame, Illumination of wire frame The colour or sh...

Illumination of wire frame The colour or shade that a surface appears to the human eye depends primarily on three  factors : Colour and strength of incoming illumination

Techniques of representing polynomials using arrays, Q. Explain any three m...

Q. Explain any three methods or techniques of representing polynomials using arrays. Write which method is most efficient or effective for representing the following polynomials.

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