3. [10 marks] We now modify the problem in Question 2 slightly by not requiring
ID: 3888760 • Letter: 3
Question
3. [10 marks] We now modify the problem in Question 2 slightly by not requiring i,j and k to be distinct. More precisely, the output of the algorithm is'yes" if there exist three indices i, j and k, with 1-i, j, K-n, such that Ali] + AIj] + A t, and "no" otherwise For example, if AI1..7]-[28,-70,-23, 92, 56,-33,-77 and t--173, the answer would be "ves". because if we set i - 2 , 1-2, and k = 6, we have A[i1+ALj1+Akl 70-70-33 =-173 (a) [5 marks] Use the algorithm design paradigm of "reduce to known problem" to give an algorithm solution that uses (n2 lg n) time. (Hint: compute the following two sets of num bers: one set contains all possible values of A + A and the other set contains all possible values of t - A[k]) (b) [5 marks] Further give an O(n2)-time algorithmExplanation / Answer
Please find my answer.
a)
Time Comlexity: O(n^2logn)
Using Sorting and Binary Search
Algorithm:
1. sort input array - (nlogn)
2. use two loops:
for (int i = 0; i < arr_size-2; i++)
{
// Fix the second element as A[j]
for (int j = i+1; j < arr_size-1; j++)
{
int seachKey = sum - (A[i] + A[j]);
int index = binarySearch(arr, j+1, arr_size, );
if(index >= 0) {
print "triplet is arr[i], arr[j] and arr[index]""
}
}
}
Time complexity:
outer for loop: O(n-2)
inner for loop: O(n-1)
binary search: O(logn)
Total time : O(n*n*logn)
b)
Time Comlexity: O(n^2)
1) Sort the input array.
2) Fix the first element as A[i] where i is from 0 to array size – 2.
After fixing the first element of triplet, find the other two elements using:
2.1) Initialize two index variables to find the candidate
elements
(a) Initialize first to the leftmost index: l = i
(b) Initialize second the rightmost index: r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == (sum - A[i])) then return 1
(b) Else if( A[l] + A[r] < (sum - A[i]) ) then l++
(c) Else r--
Time complexity:
outer for loop: O(n-2)
inner for loop: O(n)
Total time : O(n*(n-1)) => O(N^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.