3 ms·
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 th
by 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 agoOh, yeah. Thanks for the clarification.