1–8 of 8 posts
EDIT: Each point {pi} is unique.
We're talking euclidean distance measure, right? If you are performing many queries against the same set of points {pi}, then yes. Create a structure such as a BSP or quadtree containing all N points {pi} in O(n log n) time, then you can perform a single search of it in O(log n) time. You'll have a bit of extra bookkeeping since it's possible that points closer than the "best point so far" could lie within more than…
We're talking euclidean distance measure, right? If you are performing many queries against the same set of points {pi}, then yes. Create a structure such as a BSP or quadtree containing all N points {pi} in O(n log n) time, then you can perform a single search of it in O(log n) time. You'll have a bit of extra bookkeeping since it's possible that points closer than the "best point so far" could lie within more than…
That's great. Thanks for your suggestion on BSP/Quadtree and Yes, we're talking about the Euclidean distance measure. The Inputs points {p1,p2,..,pN} are given as an Array and to perform the search in the order O(logN), as you said we are supposed to construct the BSP or Quadtree which takes O(NlogN) time. when it's put together it will cost us O(NlogN) time i.e. O( NLogN + logN ). But according to the problem, all o…
The big O for (log n + c) is O(log n).
Earlier quoted context omitted.
That's great. Thanks for your suggestion on BSP/Quadtree and Yes, we're talking about the Euclidean distance measure. The Inputs points {p1,p2,..,pN} are given as an Array and to perform the search in the order O(logN), as you said we are supposed to construct the BSP or Quadtree which takes O(NlogN) time. when it's put together it will cost us O(NlogN) time i.e. O( NLogN + logN ). But according to the problem, all o…
There is no general sorting algorithm that is faster than O(n log n) worst case. But when sorting only happens once then the value of (n log n) is a constant and the running time of search is (log n + c) where c is some fraction of (n log n) amortized across each (log n) search. The big O for (log n + c) is O(log n). However, you can do better by memoizing the search to get O(1) speed in exchange for O(n) space. But…
Earlier quoted context omitted.
There is no general sorting algorithm that is faster than O(n log n) worst case. But when sorting only happens once then the value of (n log n) is a constant and the running time of search is (log n + c) where c is some fraction of (n log n) amortized across each (log n) search. The big O for (log n + c) is O(log n). However, you can do better by memoizing the search to get O(1) speed in exchange for O(n) space. But…
I'm a beginner in Algorithms. can you please explain this "But when sorting only happens once then the value of (n log n) is constant" ? is it a good practice to assume that as a constant? because we usually see the problem as a whole and individually compute its running time like sorting (NlogN)+ search (logN) to get the final running time as O(NlogN). we can solve the problem in O(N) time which's nothing but findin…
[a] represents the idea that there may be an arbitrary number of steps in the portion of the program that is proportional to [log n]
[c] represents the idea that there is a constant amount of running time overhead that is independent of the core efficiency of the algorithm.
Big O notation is convenient because it gets rid of [a] and [c]. It can be misleading because [a] and [c] might dominate the run time in all practical cases. It can also be misleading because as [n] becomes large, O(n log n) often approximates (a log n).
Here we are only doing one O(n log n) operation...so long as the sorted array is memoized and used for future operations. Note that if the array is sorted destructively, then the memory is [a' * n] or O(n} which is the same as having an unsorted array (though [a'] may be bigger than the factor required without sorting.
Anyway, I don't really know what is or isn't a naive solution. But I've read a bit of Knuth and I don't think he would encourage looking for unneeded complexity because algorithms and computer science are hard enough just taking the simplest approach.
Earlier quoted context omitted.
I'm a beginner in Algorithms. can you please explain this "But when sorting only happens once then the value of (n log n) is constant" ? is it a good practice to assume that as a constant? because we usually see the problem as a whole and individually compute its running time like sorting (NlogN)+ search (logN) to get the final running time as O(NlogN). we can solve the problem in O(N) time which's nothing but findin…
I am a beginner as well. The actual worst case time of an algorithm with big O notation of O[log n] is [(a * log n) + c] where: [a] represents the idea that there may be an arbitrary number of steps in the portion of the program that is proportional to [log n] [c] represents the idea that there is a constant amount of running time overhead that is independent of the core efficiency of the algorithm. Big O notation is…