algorithm - Find the i-th greatest element -

i want use divide-and-conquer procedure computation of i-th greatest element @ row of integers , analyze asymptotic time complexity of algorithm.

algorithm ith(a,low,high){    q=partition(a,low,high);    if (high-i+1==q) return a[q];    else if (high-i+1<q) ith(a,low,q-1);    else ith(a,q+1,high); } 

is right? if so, how find time complexity?

the time complexity described following recurrence relation:

t(n)=t(n-q)+t(q-1)+Θ(n)

but how can solve recurrence relation, without knowing value of q?

or there algorithm less time complexity computes i-th greatest element @ row of integers?

this variation of quick select algorithm (which finds i-th smallest element rather i-thgreatest element). has running time of o(n^2)in worst case, , o(n) in average case.

to see worst case, assume searching nth largest element, , happens algorithm picks q largest element in remaining range. calling ith function n times. in addition partition subroutine takes o(n) total running time o(n^2).

to understand average case analysis , check explanation given professor tim roughgarden here.