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

Graph, adjacency multilist

adjacency multilist

Structured programming, What do you understand by term structured programmi...

What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

Linked list, How to creat ATM project by using double linked list?

How to creat ATM project by using double linked list?

Rl rotation - avl tree, Example: (Double left rotation while a new node is ...

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

Write a program to create a hashed file, Write a program to create a hashed...

Write a program to create a hashed file that stores the records currently in the file " data_2013 ". Records should use the same fixed-length schema given previously, and should ag

Array implementation of a queue, Since the stack is list of elements, the q...

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Determine the space complexity of euclid algorithm, 1)      Why space compl...

1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

Determine about the logic gates, Determine about the logic gates Many e...

Determine about the logic gates Many electronic circuits operate using binary logic gates. Logic gates essentially process signals that represent true or false or equivalent i.

Adjacency matrix of an undirected graph, 1) What will call a graph that hav...

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

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