Finding a specific ratio in an unsorted array. Time complexity

Question

This is a homework assignment.

The goal is to present an algorithm in pseudocode that will search an array of numbers (doesn't specify if integers or >0) and check if the ratio of any two numbers equals a given x. Time complexity must be under O(nlogn).

My idea was to mergesort the array (O(nlogn) time) and then if |x| > 1 start checking for every number in desending order (using a binary traversal algorithm). The check should also take O(logn) time for each number, with a worst case of n checks gives a total of O(nlogn). If I am not missing anything this should give us a worst case of O(nlogn) + O(nlogn) = O(nlogn), within the parameters of the assignment.

I realize that it doesn't really matter where I start checking the ratios after sorting, but the time cost is amortized by 1/2).

Is my logic correct? Is there a faster algorithm?

An example in case it isn't clear:

Given an array { 4, 9, 2, 1, 8, 6 }

If we want to seach for a ratio of 2:

1. Mergesort { 9, 8, 6, 4, 2, 1 }

2. Since the given ratio is >1 we will search from left to right.

2a. First number is 9. Checking 9 / 4 > 2. Checking 9/6 < 2 Next Number. 2b. Second number is 8. Checking 8 / 4 = 2. DONE

Answer 1

The analysis you have presented is correct and is a perfectly good way to solve this problem. Sorting does work in time O(n log n), and 2n binary searches also takes O(n log n) time. That said, I don't think you want to use the term "amortized" here, since that refers to a different type of analysis.

As a hint for how to speed up your solution a bit, the general idea of your solution is to make it possible to efficiently query, for any number, whether that number exists in the array. That way, you can just loop over all numbers and look for anything that would make the ratio work. However, if you use an auxiliary data structure outside the array that supports fast access, you can possibly whittle down your runtime at the cost of increasing the memory usage. Try thinking about what data structures support very fast access (say, O(1) lookups) and see if you can use any of them here.

Hope this helps!

Answer 2

to solve this problem, only O(nlgn) is enough

step 1, sort the array. that cost O(nlgn)

step 2, check whether the ratio exists, this step only needs o(n)

u just need two pointers, one points to the first element(smallest one), another points to the last element(biggest one).

calculate the ratio.

if the ratio is bigger than the specified one, move the second pointer to its previous element.

if the ratio is smaller than the specified one, move the first pointer to its next element.

repeat the above steps until:

1. u find the exact ratio, or

2. either the first pointer reaches the end, or the second point reaches the beginning

Answer 3

The complexity of your algorithm is O(n²), because after sorting the array, you iterate over each element (up to n times) and in each iteration you execute up to n - 1 divisions.

Instead, after sorting the array, iterate over each element, and in each iteration divide the element by the ratio, then see if the result is contained in the array:

• division: O(1)
• search in sorted list: O(log n)
• repeat for each element: n times

Results in time complexity O(n log n)

In your example:

• 9/2 = 4.5 (not found)
• 8/2 = 4 (found)

Answer 4

(1) Build a hashmap of this array. Time Cost: O(n)

(2) For every element a[i], search a[i]*x in HashMap. Time Cost: O(n).

Total Cost: O(n)