Question

Devise an algorithm that finds all equal pairs of sums of two terms of a sequence of n numbers, and determine the worst-case complexity of your algorithm.

Short answer

$$\begin{gathered} x_1,x_2,\dots .x_n \\ i=1 \\ j=i+1 \\ k=1 \\ m=k+1 \\ {a}_i+a_j+a_m \\ i\ne k \\ j\ne m \\ (i,j)(k,l) \\ O\left(n^4\right) \end{gathered}$$

Step-by-step solution

Algorithm

we call the algorithm “paireqalsum” and the input of the algorithm is a sequence of n numbers$x_1,x_2,....x_n$

procedure pairequalsum$(x_1,x_2,....x_n:$ numbers with$n\ge 1)$

we define each four pair of elements$x_i,x_j,x_k,x_l$and check whether the sum of two pairs are equal (while we the pair are equal (while we require the pairs of elements to be different)if we find such two pairs then we print these two pairs

$i=1$to n

$j=i+1$to n

$k=1$to n

$m=k+1$ to n

$a_i+a_j+a_m$and$i\ne k$ and$j\ne m$

Print $(i,j)$and $(k,l)$

Worst case

Combining these steps we then obtain the algorithm

procedure$(x_1,x_2,....x_n:$ numbers with$n\ge 1)$

$(x_1,x_2,....x_n:n\ge 1)$

$i=1$to n

$j=i+1$to n

$k=1$to n

$m=k+1$to n

$a_i+a_j+a_m$and$i\ne k$ and$j\ne m$

Print$(i,j)$ and$(k,l)$

since we have four for loops and each loop is iterated at most n times the time complexity of the combined for loops is$O(n\cdot n\cdot n\cdot n)=O\left(n^4\right)$ .