usaar33
BAN USERI suspect this is impossible under strict definitions of O(1) space. There exist no sorting algorithms with worst-case parameters of O(n) time and O(1) space. Any solution to this problem would allow you to do a linear time, constant space counting sort where the range_of_numbers <= length of array. If you could do that, you should publish a paper.
As noted in comments I've made on other answers (e.g. storing negative numbers or a number larger than len(N) in an element), all solutions thus far provided stretch the definition of O(1) space and in the general sense are O(N).
While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
- usaar33 July 31, 2013While very clever, this is an O(n) space algorithm. You are assuming you have additional free bits to add N in which may not be true. Standard complexity analysis would show this as O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
- usaar33 July 31, 2013@varun, etc: While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
- usaar33 July 31, 2013
RepI am a management dietitian who plans food programs . I use personal counselling , cooking demonstrations, lectures and workshops as a ...
Repthelmasaraht, Applications Developer at Accolite software
A child protection social worker is responsible for a variety of services designed to help families and children in a ...
Repgaryllamasg, Backend Developer at Adjetter Media Network Pvt Ltd.
Filling in as an office agent at Mode O'Day here I learned various things here , or Office Administrator, is ...
RepRoseLeen, abc at 8x8
I am a strongly seasoned and handworking entry level graphic designer with extraordinary creative thinking and project design abilities. I ...
RepHaleyTorres, abc at A9
I am an enterprising Corporate Accountant proficient in generally accepted accounting principles including use of the latest industry standard software ...
RepAlvaPolly, Animator at ADP
I am Alva , working as a Brand Specialist with two years experience in Keeney's. I’ve excellent communication and ...
@xuzheng:
- usaar33 July 31, 2013To show that your algorithm (as a general algorithm) is O(n) space, let's use a simple counter-example. Java's a little weird in that you don't have unsigned types, so let's use C.
void elements(unsigned char * A) {
...
//Issue #1
A[i] = -1;
//Issue #2
A[A[i] - 1]--;
Let's say A has 255 elements; the domain for input numbers is 1-255. The issue #X lines both are problematic. You are going to underflow, as a negative is outside the domain. The subtraction creates a large positive number indistinguishable from your original input data -- causing the algorithm to fail.
This isn't so obvious if you use Java, as all integers in Java are signed. In this particular language, you just happen to have that an extra bit of unused space in each element in the input array which you can use for your purposes. But this is not true in general (as in the C example given above).
You cannot rely on such the input array being inefficiently stored. If it is efficiently stored (e.g. as an unsigned type), you must allocate N new bits to store that "count or input" flag.. making it an O(N) space algorithm.