a) Develop well-documented pseudo code that finds all the two elements of a give

Question

a) Develop well-documented pseudo code that finds all the two elements of a given array that subtract exactly to |x| (absolute value of x) using a stack or queue. The code must display the indices and the values of these elements. For instance, given the following array (13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46) and x as 8, your code should find and display something similar to the following (notice that this is just an example. Your solution must not refer to this particular example): All pairs of elements of the array that subtract exactly to absolute value of 8 are: Indices 0 & 3 with values 13 & 21 (e.g., 13-21= | 8 |) Indices 1 & 5 with values 1 & 9 Indices 2 & 4 with values -8 & 0 Indices 6 & 10 with values -54 & -46 Etc.

b) What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity.

c) What is the Big- complexity of your solution? Explain clearly how you obtained such complexity.

d) What is the Big-O space complexity of the utilized stack or queue? Explain your answer.

Explanation / Answer

Answer:-

(a)As we need to find the absolute subtraction of two values in array whose result should be equal to given number x. We will use two for loop in first loop we take an element and in second loop we take one by one element and subtract this from outer loop element are absolute value if equal to x then we print the result.

Algorithm:

given Array A[0..N-1]

given value x

print -> "All pairs of element of the array that subtract exactly to absolute value of X are: "

for i -> 0 to N-2

for j -> i+1 to N-1

if abs(A[i] - A[j] equal to x then

print -> "Indices i & j with values A[i] & A[j] "

// above algorithm will print all pairs in Array A with given condition.

(b) As we have two for loop. Outer loop run through 0 to N-2 and inner loop run through i+1 to N-1.

for i= 0

              inner loop run N-2 times

              for i=1

             inner loop run N-3 times

             for i = N-2

             inner loop run N-1-(N-2) times -> 1 times

So Time complexity is O(n^2).

c) Big sigma complexity is also same as big O complexity

   (n^2).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.