Question

a. Use pseudocode to specify a brute-force algorithm that takes as input a list of n positive integers and determines whether there are two distinct elements of the list that have as their sum a third element of the list. That is, whether there exists i, j.k such that iヂj, i关k,j关k and ai + aj = ak. The algorithm should loop through all triples of elements of the list checking whether the sum of the first two is the third b. Analyze the worst-case time complexity of the algorithm in part (a) c. Devise a more efficient algorithm for solving the problem in part (a) that first sorts the list and then checks for each pair of terms whether their difference is in the sequence. Express your algorithm in pseudocode d. Analyze the worst-case time complexity of the algorithm in part (c) Is it more efficient than the algorithm in part (a?

Answer 1

PRO&AM: Check, End End o End n -take On2) -time
Yes second algorithm is more efficient than first as it is O(nsquare) than iin 1 which was O(n cube)