Give an algorithm in pseudocode for finding the largest sum of any pairs of integer numbers in a given sequence. For instance, if the input sequence is (3, 7, 1, 23, -13), the output has to be 30 (sum of 23 and 7).

 The Lines 1,2, 10 and 11 are operations that are executed only once: 1 operation The outer loop in Line 3 is executed n times: n operations. Lines 4-9 execute a constant number of times for each iteration of the loop, so we can treat them as a single operation that executes n times. The inner loop in Line 4 contains conditional statements, which are executed in constant time, so the total time complexity of the inner loop is constant. Therefore, the total time complexity of the algorithm is 2n + 1.

Transcribed Image Text:

Give a more efficient algorithm for the same problem that will iterate over the input sequence only once. 1: maxsum1 := -∞ // initialize with a value that is smaller than the result 2:maxsum2 := -- // initialize with a value that is smaller than the result 3: for i:= 1 to n // iterate over each element in the input sequence 4: if a[i] > maxsum1 5: maxsum2 := maxsum1 6: maxsum1 = a[i] 7: else if a[i]> maxsum2 maxsum2 := a[i] 8: 9: end if 10: end for 11: return maxsum1 + maxsum2 // return the sum of the two largest numbers Give a more efficient algorithm for the same problem that will iterate over the input sequence only once. 1: maxsum1 := -∞ // initialize with a value that is smaller than the result 2:maxsum2 := -- // initialize with a value that is smaller than the result 3: for i:= 1 to n // iterate over each element in the input sequence 4: if a[i] > maxsum1 5: maxsum2 := maxsum1 6: maxsum1 = a[i] 7: else if a[i]> maxsum2 maxsum2 := a[i] 8: 9: end if 10: end for 11: return maxsum1 + maxsum2 // return the sum of the two largest numbers

Answer rating: 100% (QA)

Solution Pseudocode for the more efficient algorithm 1 maxsum initialize with a value that is smalle... View the full answer