The problem is to solve it in n+logn−2 (base 2) no of comparisons.
My algorithm is taking some extra space less then (O(n*n)). How can i reduce this extra space without increasing the complexity.
comparisionarray= (2D array ) //a function to find the largest. findlargest(a,b) if(len(a)==1 and len(b)==1) append b to array at ath index in comparisonarray. append b to array at bth index comparisionarray. return max(a,b) else return max(findlargest(1stHalfof(a),2ndHalfof(a)),findlargest(1stHalfof(b),2ndHalfof(b)) input= input_array() largest=findlargest(1stHalfof(input),2ndHalfof(input)) subarray=[array at index largest in comparisionarray] 2ndlargest=findlargest(1stHalfof(subarray),2ndHalfof(subarray)) print(2ndlargest)
Edit: It can be done in minimum n+logn−2 comparisons. That is the only condition . This answer on math.stackexchange.com proves it. It has been generalized for nth largest element
Seems that there is a solution at this link stackoverflow. But i am not sure about the extra space and time complexity.