Consider the following problem. We are given two arrays, A[I].Aln] and B[1]..BIn
ID: 3870581 • Letter: C
Question
Consider the following problem. We are given two arrays, A[I].Aln] and B[1]..BIn], each holding positive integer keys (possibly with duplicates). The arrays are of the same size, and each is sorted. We are also given a positive integer s, and we want to find a pair (i.j) of indices such that Ali] + BJ] = do. If no such pair exists then we want that indicated, in the form of (0,0), a non-valid pair of indices, being returned. Using neat, clean pseudo-code, write three different functions to solve the problem: s. If several such pairs exist, we do not care which is produced any such pair will 1. A brute-force function F1(A, B,,. The worst-case running time of F1 should be 2. A function F2 (AH. BH. n. s). The worst-case running time of F2 should be (n log n). Make 3. A function F3(A1.1. BH. n, s). The worst-case running time of F3 should be en). Make F3 (n2). Make F1 as simple and neat as you can. F2 as simple and neat as you can. as simple and neat as you can.Explanation / Answer
Solution:
1)
Two nested loops are there which are running n number of times each that is why this bruteforce method will take O(n^2) time.
2)
In the above pseudo code the inner loop will be running log n number of times since it is searching for the other element using binary search and jumping around in the sorted array to get the result.
3)
The above algorithm will be finished in O(n) time.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)