4 ms·

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 t

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 finding the Euclidean distance to Each Point and keeping the Min. distance in memory. but that's regarded as a Naive solution.

brudgers 9y ago
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 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.
- heythisisom 9y ago
  Oh, yeah. Thanks for the clarification.

brudgers 9y ago

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 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.

heythisisom 9y ago
Oh, yeah. Thanks for the clarification.