[ Java - PriorityQueue ] analyze time complexity of this code. Many thanks! Back

Question

[Java - PriorityQueue] analyze time complexity of this code. Many thanks!

Background:

Given an array containing N points find the K closest points to the origin (0, 0) in the 2D plane. You can assume K is much smaller than N and N is very large.

E.g: given array: (1,0) (3, 0),(2, 0), K = 2

Result = (1,0), (2, 0)

(result should be ascending order by distance)

Code is:

Question:

1: What is time complexity for line 35, line 39, independently and separately?

2. What is time complexity for line 35 - 39 (As a whole) ?

3. What is time complexity for line 44 - 46 (As a whole) ?

4. What is overall time complexity for entire method getKNearestPoints(), in best, worst and average case? What if n >> k ? and what if we don't have n >> k ?

Background:

Given an array containing N points find the K closest points to the origin (0, 0) in the 2D plane. You can assume K is much smaller than N and N is very large.

E.g: given array: (1,0) (3, 0),(2, 0), K = 2

Result = (1,0), (2, 0)

(result should be ascending order by distance)

Explanation / Answer

Here is your Answers:

Answers:

Queue here is based on Max Heap implementation.So, complexities are as follows:

Answer 1: Line 35:Time complexity for line 35 will be O(log k), the time to insert an element in the heap. Bottom up approach is followed in the heap at the time of insertion.

Line 39: Time Complexity will be O(log k), the time to remove the head of the heap, the heapify approach at the root of the heap is applied to remove the top of the heap.

Answer 2: Line 35-39: From the above complexities we can see that the overall complexity of the loop will be O(log k). This loop runs for n elements, so the overall complexity will be O(n log k)

Answer 3: Line 44-46: The complexity of checking the size of the heap is again O(1), and polling is O(log k). So we are doing polling k times. The overall complexity of the loop will be O(k log k).

Answer 4:Overall complexity will remain O(n log k).

I hope this solves your problem

Comment if you have any problem in above answer

And please give it a thumbs up if it solved your problem :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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