If you are doing a fixed portion k of an array of size n, your algorithm is O(n). The constant gets worse the closer that k is to 1. Unless my back of the envelope calculation is wrong your constant is proportional to k-log(1-k) where that logarithm is the natural log. Throw in the fact that you are only selecting k*n elements that works out to your selecting things 1-(log(1-k)/k) times for every output (on average). If I put in k = 0.9 that works out to be a factor of about 3.56.

So while if you are selecting all but a few elements, your approach is slow, if you are selecting up to a fixed proportion, it should be just fine.