title: Find time complexity of an element which is neither kth maximum nor kth minimum?
body: <p>There are <strong>N</strong> distinct numbers which are given not in sorted order. How much time it will take to select a number say <strong>which is neither k-th minimum nor k-th maximum</strong>?</p>
  
  <p><strong>I tried like this =></strong></p>
  
  <p>Take initial k + 1 numbers and sort them in O(k log k). Then pick up kth number in that sorted list, that will be neither the kth minimum nor kth maximum .</p>
  
  <p><strong>Hence, time complexity = O(K log k)</strong></p>
  
  <p><strong>Example =></strong> </p>
  
  <p>Select a number which is neither the 2nd minimum nor 2nd maximum.</p>
  
  <p>array[] = {3,9,1,2,6,5,7,8,4}</p>
  
  <p>Take initial 3 numbers or subarray = 3,9,1 and sorted subarray will be = 1,3,9</p>
  
  <p>Now pick up 2nd element 3. Now, 3 is not the 2nd minimum nor 2nd maximum .</p>
  
  <p><strong>Now, time complexity = O(k lg k) = O(2 lg 2) = O(1).</strong></p>