complexity of algo
Posted on 2003-10-31
I got some questions about complexity of shell sort and heap sort
I know worse case, average case of heap sort id O(n log n)
um...i'm just woundering whether the best case is also nlogn, and what if he complexity of heap sort for a sorted file..( i think those two stillO(nlogn), cos bulild the heap: O(n) + sort the heap still(log n) no matter the file is sorted or not)
but I'm not sure....
why the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?