Clash Royale CLAN TAG#URR8PPP

Analysis for query d-dimensional points via comparison points

I have been thinking about higher dimensional point searching and the trade-offs of different structures. But I am also curious roughly how much improvement I am having by considering different implementations.

My bigger question is if all the effort worth it as try to figure out the query asymptotic for the naive implementation. The naive implementation would feature d sorted arrays of each of the n elements. Binary search every on each array and compare all the points in the correct range across the d dimensions.

When d = 2, this algorithm should be O(n^2) because of the comparison of points in each array. But what will query be for any d dimension? I think it should be O(n^d) as we need to compare the set of points already approved in the previous d - 1 dimensions and I feel that this could be shown by induction, but I am queasy about in nonetheless.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.