Do the following two problems 1 Any algorithm that solves th

Do the following two problems:

1. Any algorithm that solves the search problem for a 7654 element list by comparing the target element x to the list items must do at least __________ comparisons in the worst case.

2. Any algorithm that sorts a 7 element list by comparing pairs of items from the list must do at least __________ comparisons in the worst case.

Solution

If the element is not in the list, the only way to know it is to compare it against every item present in the list. If there are n elements, then the sequential search requires n comparisons to discover that the item is not there. In the case where the item is in the list, the analysis is not so straightforward. There are actually three different scenarios that can occur. In the best case we will find the item in the first place we look, at the beginning of the list. We will need only one comparison. In the worst case, we will not discover the element until the very last comparison, the nth comparison.

So, Any algorithm that solves the search problem for a 7654 element list by comparing the target element x to the list items must do at least __7654__ comparisons in the worst case.

Next,the algorithm for bubble sort or pair sort requires a pair of nested loops. The outer loop must iterate once for each element in the data set (of size n) while the inner loop iterates n times the first time it is entered, n-1 times the second, and so on. Consider the purpose of each loop. Bubble sort is structured so that on each pass through the list the next largest element of the data is moved to its proper place. Therefore, to get all n elements in their correct places, the outer loop must be executed n times.

And on the first iteration of the outer loop, while trying to place the largest element, there have to be n - 1 comparisons: the first comparison is made between the 1st and 2nd elements, the second is made between the second and third elements, and so on until the (n-1)th comparison is made between the (n-1)th and the nth element. On the second iteration of the outer loop, there is no need to compare the against the last element of the list, because it was put in the correct place on the previous pass. Therefore, the second iteration requires only n-2 comparisons. This pattern continues until the second-to-last iteration of the outer loop when only the first two elements of the list are unsorted so, only one comparison is necessary. The total number of comparisons, therefore, is (n - 1) + (n - 2)...(2) + (1)

= n(n - 1)/2 or O(n 2).

So, any algorithm that sorts a 7 element list by comparing pairs of items from the list must do at least __21________ comparisons in the worst case.