Algorithm Analysis Consider searching algorithms on the following array of data:
ID: 3530720 • Letter: A
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
please rate
(a)..since the given array is not sorted we have to use sequential search .In sequential search every array element is compared one by one with the element to be searched,which is in our case is 19.The code for sequential search is shown below
int sequentialSearch(int* a,int n,int x)
{
for(int i=0;i<n;i++)
if(a[i]==x)
return 1;
else
return 0;
}
so first 22 will be compared with 19 ,after that 21 will be compared with 19, then 9,4,16..so on untill 19 is not found
(b)..search time complexity in case of above example
1.sequential-search (o)(n) 12
2.binary search (o)(lgn) not applicable beacuse the array element is not sorted
(c)..Binary search requires that the data to be searched must be sorted either in increasing order or decreasing order.The code for binary search is
int binarySearch(int* a,int n,int x)
{
int low =0;
int high=n;
mid=low+high/2;
while(low<=high)
{
if(mid==a[x])
return 1;
else if(mid<a[x])
low=mid+1;
else
high=mid-1;
}
return 0;
}
d).8-72, 10--110, 20--420 so in case of n the time complexity will be (o)(n(n+1))
e).array size time
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
the running time will be (o)(n^2)
explaination:--1+2+3+4+5+6........+n = n(n+1)/2 airtmetic progression
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.