Randomized Select

If r is not between i and j, there's no point in sorting...

int select( vector<int> & data, int i, int j, int r )
{
  if( i == j )
    return data[r];

  int l = rando.RandInt( i, j );
  int k = partition( data, i, j, l );
  
  if( k == r)
    return data[r];

 if( r < k )
   return select( data, i, k-1, r );
 else
   return select( data, k+1, j, r );
}

Show that the expected running time is O(n) [HW].