Develop and analyze an iterative version of Sequential Search (Search(A, k, p, r
ID: 3841126 • Letter: D
Question
Develop and analyze an iterative version of Sequential Search (Search(A, k, p, r) that returns the position of k in the sorted integer array A[p ... r]. If k is not found, the algorithm returns -1. For your algorithm perform the following specific tasks:
Give pseudocode for your iterative Search(A, k, p, r) algorithm. NOTE: You may not use global variables in your algorithm.
Perform a line-by-line analysis of your algorithm and derive a precise expression T(n) for the running time, where n is the length of the array. You may assume that each line of pseudocode takes unit time.
Describe the situation resulting in the best-case running time of your algorithm and derive an expression for T(n) in this case. Also, give an asymptotic expression for T(n).
Describe the situation resulting in the worst-case running time of your algorithm and derive an expression for T(n) in this case. Also, give an asymptotic expression for T(n).
Develop and analyze a recursive version of Binary Search (BSearch(A, k, p, r)) algorithm that uses a divide-and-conquer approach to perform a search for k (returns the position of k in the array or return -1 if k is not found) in which the algorithm divides the sorted array in half and calls itself recursively on each half. For your algorithm perform the following specific tasks:
Give pseudocode for your recursive BSearch(A, k, p, r) algorithm. NOTE: You may not use global variables in your algorithm.
Perform a line-by-line analysis of your algorithm. Describe the situations resulting in the best-case and worst-case performances of your algorithm.
Derive a precise recurrence for T(n) in the worst case, and solve the recurrence.
The following chart shows the run time of algorithms that use f(n) operations to run on a computer where each operation takes one second to execute. Fill in the blanks in the chart.
n
f(n)=log2n
f(n)=n
f(n)=n log2n
f(n)=n2
f(n)=2n
10
3.3s
10s
33.0s
100s
1024s
20
50
100
1000
10000
For each of the following, answer "yes", "no", or "cannot tell". Explain your reasoning.
Is n3 = O(n2) ?
Is n3 = W(n2)?
Arrange the following expressions by growth rate from slowest to fastest.
4n2
n!
log3n
3n
20n
2
log2n
n
f(n)=log2n
f(n)=n
f(n)=n log2n
f(n)=n2
f(n)=2n
10
3.3s
10s
33.0s
100s
1024s
20
50
100
1000
10000
Explanation / Answer
Okay, the question is quite long. Let's answer it part by part:
Part 1: Linear or Sequential Search
int search(int A[],int k, int p, int r)
Set found=-1
while(i from p to r && found = -1)
if(A[i] == k) found = i
else i = i +1
end while
return found
So, we have to define a function that take array of elements, element to be searched, starting index and ending index. This function will return the index of the element if found. Define a variable found that will store the index. Initiate it with -1, if not found then it will return -1. Run a loop for starting index to ending index and compare each variable, if there is a match quit and return the index.
T(n) = T(n-1) + 1 i.e. time to search n elements is the time to examine 1 element plus the time to search the remaining elements (n-1).
BestCase: Element found at first position in that case
T(n) = O(1)
Worst Case: Element found at the last position in that case
T(n) = O(n)
Part 2: Binary Search
int BSearch(int A[],int k, int p, int r)
if (r >= p)
int middle = p + (r - p)/2;
if (A[middle] == k) return middle;
if (A[middle] > k) return BSearch(A, k, p, middle-1)
return binarySearch(A, k, middle+1, r)
return -1;
return -1;
One thing about binary search is that it can only be applied on sorted array, so we define the signature of the function and check if the ending value is greater than or equal to the starting value. If it is then proceed with the function otherwise return -1. The function creates a middle index and checks if it is equal to the required element. If it is then return the middle index. If the middle value of the array is greater than the required element then we have to search the left part of the array so we do a recursion with p and ending index as middle-1. The case left is when middle value is less than required element in that scenario we have to search the right part of the array hence, we pass the parameters middle +1 and r.
T(N) = T(N/2) + 1 i.e. the time to search in the array of N/2 elements plus 1 comparison.
Best Case: The element is found at first iteration and that to in the middle, in that case: T(N) = O(1)
Worst Case: The element is found at first or last position in that case: T(N) = O(log n)
T(N) = T(N/2) + 1
T(N/2) = T(N/4) + 1
T(N/4) = T(N/8) + 1
T(4) = T(2) + 1
T(2) = T(1) + 1
So, we sum up the left and right side
T(N) = T(N/2) + T(N/4) + T(N/8) + … +T(2) + T(1) + (1 + 1 + … + 1)
T(N) = 1 + log n
T(N) = O(log n)
Is n3 = O(n2) ? No, n3 can't contain n2
Is n3 = W(n2) ? Yes
Actually, it is quite difficult to say what is written here but still I will try to arrange it
2
log2n
log3n
3n
20n
4n2
n!
For further doubts, please comment !
n log2n n n log2n n2 2n 10 3.3s 10s 33.0s 100s 1024s 20 4.322 20 86.4 400 1048576 50 5.644 50 282.2 2500 1.1259e15 100 6.644 100 664.4 10000 1.267651e30 1000 9.966 1000 9966 1000000 1.071509e301 10000 13.288 10000 132880 108 a very large numberRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.