Develop welldocumented pseudo code that finds all the two el

Develop well-documented pseudo code that finds all the two elements (non-negative numbers) of a given array that modulo up exactly to x. The code must display the indices and the values of these elements. For instance, given the following array (123, 73, 39, 12, 14, 9, 113, 93, 203, 22, 25, 10) and x as 3, 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 modulo up to a value of 3 are: Indices 0 & 3 with values 123 & 12 (e.g., 123 % 12 returns 3) Indices 1 & 5 with values 73 & 14 Indices 2 & 4 with values 39 & 9 Indices 6 & 11 with values 113 & 22 etc. b) Briefly justify the motive(s) behind your design. c) What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity. d) What is the Big-Ohm complexity of your solution? Explain clearly how you obtained such complexity. Given a non-sorted array A of n integer and an integer value x: a) Similar to Question 1, develop well-documented pseudo code that finds all pairs of elements of the array that modulo up exactly to x. The code however must be different than the one you had in Question 1 and must use either a stack S or a queue O to perform what is needed. b) Briefly justify the motive(s) behind your design. c) What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity. d) What is the Big-Ohm complexity of your solution? Explain clearly how you obtained such complexity. e) What is the Big-O space complexity of the utilized stack or queue? Explain your answer.

Solution

a) Pseudo code

1. Let A be the array of elements holding non negative numbers
2. Let n, i, j, x are integer variable
3. scan the value of x
4. n is the size of the array A
5. for each i from 0 to n
   i. for each j form 0 to n
       a. if(a[i] % a[j] == x )
           A. Print Indices i and j with value A[i] and A[j]

b) Big-O Complexity
Big-O complexity theory gives us tight upper bound. That means it signifies that for asymptotic input size of n what is the maximum number of times a statement of the above program will execute.

First loop is executing n times. For each phase of first loop second loop is executing n times.
So, we can see that the print statement under second loop is being executed maximum times (n^2). And in any circumstance it can\'t execute more than n^2 times. I.e we can call it as tight upper bound of the given code.
Hence the Big-O complexity is n*n i.e O(n^2)

c. Big- Complexity
Big- complexity theory gives us tight lower bound. That means it signifies that for asymptotic input size of n what is the minimum number of times a statement of the above program will execute.

First loop is executing n times. For each phase of first loop second loop is executing n times.
So, we can see that the print statement under second loop is being executed maximum times (n^2). And in any circumstance it can\'t execute less than n^2 times. I.e we can call it as tight lower bound of the given code.
Hence the Big- complexity is n*n i.e (n^2)

Note: As tight upper bound O(n^2) and tight lower bound (n^2) is same we can also say that complexity of this code is (n^2)

-------------------------------------------------

Please note that as there is no preemption in any of both the loop that\'s why maximum running time and minimum running time is same. Because in any case both the loop will run for n times. But maximum running time and minimum running time can differ. For example if the requirement is to find only one pair instead of all pair then there could\'ve been 2 cases depending upon inputs.

First, there may be no pair exist in input array. In that case both loop will run till the end all the way up-to n times as it won\'t be able to find any pair. So, loop will run n^2 times

Second, Assume, it happened that the very first pair satisfies the condition. In that case first loop will execute 1 time and second loop also execute 1 time then it will exit from both the loop. Because we got the pair and we need only one. So, in that case loop will run only 1 time

So, clearly we can see that depending upon inputs, maximum and minimum number of running time defers. So here Maximum running time is O(n^2) and minimum running time is (1) and we can express complexity of this program with notation as maximum and minimum running time is not equal.