Randomly selecting k different numbers in a range

I need to select k elements randomly in the range 0 to n-1. n can be upto 10^9. And k can range from 1 to n-1. I can do this in O(n) time just by shuffling an array containing values 0 to n-1 and choosing first k elements from it. But when k is small this method is both time and memory inefficient. Is there any O(k) solution to this problem?