Question

You are given a set S of n real numbers where for each element x ∈ S, 1 < | x | < 10. You are also given a black box that returns true if there is some combination (x, y, z) ∈ S such that x · y = z.

Say the black box returns only z. Write an O(n log n) algorithm to find x and y. In other words, given a set S with n real numbers and a number z, write an O(n log n) algorithm to find (x, y) ∈ S such that x · y = z.

Answer 1

O(nlogn) algorithm to solve this problem:

1) Sort the set S if, they are not sorted

2) loop over the set and for each element a in the set:

    1) Find b = z/a

    2) Then, search for b in the set using Binary Search.

    3) If found return true

4) return false

Time complexity analysis of algorithm

Lets say set has n elements,

sorting the array ------ O(nlogn)          [use quick sort or merge sort or heap sort]

looping over the set   ------ O(n). And for each element a in the set, we are finding a number b such that a*b = z. For this we will use Binay Search

Binary search ------- O(logn)

So total time complexity of looping over the set and searching for a number b such that a*b = z is O(n)*O(logn) = O(nlogn)

Total time complexity of algorithm = O(nlogn)_sorting + O(nlogn)_{looping + searching =} O(nlogn)