Question

12. The reciprocal search problem is:

input: a list L of n floating point numbers
output: two elements a, b L such that a*b=1, or None if no such a, b exist

Design an algorithm for this problem using the greedy pattern. Write pseudocode for your algorithm below. If you write multiple drafts, circle your final draft. Hint: I expect your algorithm to be relatively simple and to have time complexity O(n²).

13. Perform a chronological step count to derive the time complexity T(n) of your algorithm. Show your work.

14. Write the efficiency class of your algorithm in Big-Oh notation.

Answer 1

12) Approach:

Approach is very simple. We will loop for each element in the list. For each element ia n the list, we will check the whole list from that element onwards. If there is any element b such that a*b = 1. If there's any such pair, add it to our result list. So we are greedily checking all pairs of elements in the list and pushing all such pairs where a*b = 1 to our result list.

Pseudocode will look like this:

function ReciprocalSearch(L):
    
    Declare result list, res;
    for i = 1 to n:
        for j = i to n:
            if L[j] * L[i] == 1:
                res.push(pair(L[i], L[j]))


    return res 
end

13)

Step count for algorithm:

The two for loops are nested, so their combined time complexity will be

Then total cost of algorithm is:

Substitute, C1 = c1 + c2 + c5 + c6 and    C2 = c2*c4

14) Our input length is n as we are having n floating point numbers. There are two nested loops. One is running from 1 to n and other is running from i to n. Let's break it further.

For each element, the algorithm loops for elements ahead it. So, for first element the inner loop will run n - 1 times, for second element the inner loop will run n - 2 times, for third element it will run n - 3 times. This will go on and for the last element inner loop will not run at all.

So, time complexity, T(n) = (n - 1) + (n - 1) + (n - 2) + (n - 3)+ ......... + 1

It is just the sum of n - 1 natural numbers, that is (n*(n - 1)) / 2.

T(n) = (n^2 - n) / 2

T(n) = O(n^2).

if it helps you, do upvote as it motivates us a lot!

If you have any doubt, do share in comments section.