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

Visual Basic Assignment, When writing a code for a program that basically a...

When writing a code for a program that basically answers Relative Velocity questions how do you go at it? How many conditions should you go through?

Write an algorithm inputs speed of cars using pseudocode, Write an algorith...

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

Multiple queue, algorithm for multiple queue with example program

algorithm for multiple queue with example program

Explain th term input and output- pseudocode, Explain th term input and ou...

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

Explain np-complete decision problem, a. Determine the result of inserting ...

a. Determine the result of inserting the keys 4,19, 17, 11, 3, 12, 8, 20, 22, 23, 13, 18, 14, 16, 1, 2, 24, 25, 26, 5 in order to an empty B-Tree of degree 3. Only draw the configu

Array implementation of lists, In the array implementation of the lists, we...

In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b

Advanced trees, Linked list representations contain great advantages of fle...

Linked list representations contain great advantages of flexibility on the contiguous representation of data structures. However, they contain few disadvantages also. Data structur

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?

R. Studio, I need a person who has a good background in using R. Studio? I...

I need a person who has a good background in using R. Studio? In adition, a person who is good in using algorithms.

Algorithm for finding a key by binary search technique, Q. Write down an al...

Q. Write down an algorithm for finding a key from a sorted list using the binary search technique or method.

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