4 ms·
I am curious about the run time analysis. O(log_3 n) If you have two comparisons per call to your quicksort recursive function instead of just one comparison,
by jamra 13y ago
I am curious about the run time analysis. O(log_3 n)
If you have two comparisons per call to your quicksort recursive function instead of just one comparison, are you reducing the complexity at all?
The benefit of this method is less recursive calls, therefore, less overhead of recursion.
- aidenn0 13y agoYou actually increase the complexity. 2 compares with dual-pivot reduces your search space by 2/3 2 compares with single pivot reduces your search space by 3/4 Furthermore binary search can be done iteratively unlike quicksort, so reducing recursion overhead is useless.