I have been asked this question:
Given a function which finds a median of an array in O(logN). What is the worst running time for the most efficient algorithm for implementation of quicksort.
My approach is to solve the recurrence of
T(N) = T(N/2) + log(N) + N
where log(N) is the time to find the median and N is shuffling the numbers in an array.
But I am confused as what the solution should be. My intuition tells me that it should be
T(N) = N log(N)
because in each recursion N dominates log(N). But is this the "proper" way to solve a recurrence with more than one term? If not, how should I solve this problem?