Algorithm Analysis Consider searching algorithms on the following array of data:

Question

Algorithm Analysis

Consider searching algorithms on the following array of data:

[22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13]

Suppose you want to implement a searching algorithm to see if the data set contains the number 19. Demonstrate how the search would go if you used:

A sequential search

A binary search

State the runtime for each of the searches, in this example, and for general data sets of size n. Address the issue of the order of the data in binary searching.

Suppose an algorithm that processes a data set of size 8 has a runtime of 72. The same algorithm has a runtime of 110 when applied to a data set of size 10; and when applied to a data set of size 20, it has a runtime of 420. Using big-O notation, state the runtime for this algorithm for the general case of a data set of size n.

Suppose you develop an algorithm that processes the first element of an array (length of n), then processes the first 2 elements, then the first 3 elements, and so on, until the last iteration of a loop, when it processes all elements. Thus, if n = 4, the runtime would be 1 + 2 + 3 + 4 = 10.

Create a table that depicts the runtime for arrays of length 1 to 10. Would you expect the general runtime to be O(n), O(n2), O(n3), or some other function of n? Explain.

Explanation / Answer

Concept:

Sequential Search:

It searches for the given element in an array from the first element to last element until the given element found.

It does not need sorting of the array elements.

Suppose in the given array if we want to find the element 19 ,then we need to search the elements from starting element to final element until the key found.

It takes runtime of O(n),here n is number of elements in an array .

For our example to search element 19 in the given array it takes run time O(16).

For dataset os size n it takes run time of O(n).

Binary Search:

Before applying binary search to find an element the array/list should be sorted either in descending or ascending order.

to search for an element we can split the array into two parts ,if the middle element is equal to the key then we got our element,if not there are two cmditions

1.If the key element is greater than the key just use the right side part to the middle element .

again apply same thing until we found the key

It takes O(logn) as Run time.

for our list/array it takes O(log16)

The general runtime to be O(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.