First find the ratio(profit/weight)= O(n) time
Then find median(using selection procedure)= O(n) time
Then sum the weights of all items whose value exceeds the median and call it M. If M exceeds W then we know that the solution to the fractional knapsack problem lies in taking items from among this collection. In other words, we’re now solving the fractional knapsack problem on input of size n/2. On the other hand, if the weight doesn’t exceed W, then we must solve the fractional knapsack problem on the input of n/2 low-value items, with maximum weight W − M
so the recurrence relation T(n) = T(n/2) + cn..