What are best average and worst time complexity of this algorithm called closest pair by divide and conquer

no bc

yes, this is correct. The recursive calls must be made with 2 modified Ys. One for the left points and one for the right. Or, as you suggest, by merging the points. To merge them, you would need to return not only d, but also the points merged by y coordinate

+1 @Mayank Kumar

+1 ansh arora

@@mohitmridul6164 +1

@Mayank Kumar +1

Ha bhaiya. It helped a lot . Maza aa gaya 🤗🤗

hey bro 🙂

kere mama mmk

Hola🥲

Yo....bro

hehe

Consider 5 points, 100 points, 10000 points, and let me know if you still think the formula is factorial n (hint: sum of arithmetic sequence). Then please get your fact right about Big O Notation! Keep in mind that constants are dropped when calculating time complexity.

In that case the running time would be something like n(n-1) + (n-1)(n-2) + ... + (n-k+1)(n-k) = (n^2-n) + (n^2-3n+2) + (n^2+(1-2k)n+(k^2-k)) = kn^2 + a. Where a is the sum of other lower power terms. Since big O notation drops those lower terms and constants we get that big o notation is n^2.

@@marceloenciso6665 agreed, sorry its not factorial, the formula for total number of tests is; (n squared -n) /2 So the total number of tests will always be less than HALF of n squared Anyway this divide and conquer method it still a poor way of solving the problem. Doing all those square roots is a real mess. This is how I would do it for least amount of CPU cycles; 1. Brute force all points but only testing points AFTER the point. (N squared -n) /2 tests; 1a. Get the x dist and y dist (very fast, just 2 subtractions needed) 1b. keep the larger of the two, very fast (we will call this the simple distance) 1c. Put the simple distance in a list, ordered by size (very fast) TRICK; The actual distance can never be more than the simple distance *1.41 so only need to test those list entries that are LESS then the smallest entry *1.41 Now we are only needeing to do the mults and sq roots on a tiny percentage of the point pairs; 2. Process down the ranked list; 2a. Do the pythag mult mult sq root etc to get real dist 2b. If less than prev best, save that as best 2c. If the list entry is >top entry *1.41 then job is done! Ive been coding high perf algorithms for 30 years and mostly had to do it on low perf 8bit systems with no math processor etc. The algorithm I outlined above is just my first attempt but would be far quicker than the divide and conquer system provided that n is not excessively large.

Ok, i just wrote some quick c code to test my algorithm. n = 100 points, randomly distributed x and y values using; random(1024) Brute force ranked point distances by my "simple distance" ie the largest of x1-x2 or y1-y2 (4950 tests) Then ONLY needed to do the pythag mult sqroot etc on ANY points where; simple dist

@@wizrom3046 You should really learn about big O notation before saying anything. (n squared - n) / 2 -> (n^2) /2 - n/2 -> n^2*1/2 - n*1/2 When we calculate big O notation, we only care about the *dominant terms* and we do not care about the coefficients. Thus we take the n squared as our final big O (in this case n^2 is the dominant term and you can eliminate all the other parts in the big O notation).