3 invertible bloom filter pointer

It's at least possible to test whether the input is a permutation with a randomized algorithm that uses O(1) space, always answers "yes" when it is a permutation, and answers "yes" incorrectly when it is not a permutation only with very small probability.

Simply pick a hash function $h(x)$, compute $\sum_{i=1}^n h(i)$, compute $\sum_{i=1}^n h(a[i])$, and compare the two sums.

Ok, some care needs to be used in defining and choosing among an appropriate family of hash functions if you want a rigorous solution (and I suppose we do want one, since we're on mathoverflow not stackoverflow). Probably the simplest way is just to fill another array $H$ with random numbers and let $h(x)=H[x]$, but that is unacceptable because it uses too much space. I'll leave this part as unsolved and state this as a partial answer rather than claiming full rigor at this point.

See also my paper Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton's Identitities and Invertible Bloom Filters which solves a more general problem (if there are O(1) duplicates, say which ones are duplicated, using only O(1) space) with the same lacuna in how the hash functions are defined. It also contains a proof that an algorithm that makes only a single pass over the data cannot solve the problem exactly and deterministically, but of course that doesn't apply to algorithms with random access to the input array.

Post Undeleted by David Eppstein
2 +$; added 61 characters in body; added 172 characters in body There are several easy O(n It's at least possible to test whether the input is a permutation with a randomized algorithm that uses O(1) time solutions. Firstspace, since your numbers are all in the range 1..nalways answers "yes" when it is a permutation, you can bucket sort them in linear timeand answers "yes" incorrectly when it is not a permutation only with very small probability.Second, make an array of n binary values, all initially false Simply pick a hash function$h(x)$, compute$\sum_{i=1}^n h(i)$, scan your input setting the corresponding array values to truecompute$\sum_{i=1}^n h(a[i])$, and then check that everything has been set to truecompare the two sums.Third Ok, even if you wanted some care needs to detect duplicates be used in more complex input such as a set defining and choosing among an appropriate family of real numbers, hash functions if you could use want a hash table. Theoretically, there are some proofs that in limited models of computation rigorous solution (disallowing hash tables) with real number inputs one can't and I suppose we do better than$\Omega(n\log n)$for duplicate detection: see e.g. Yao, A. C.-C. (1989), "Lower bounds for algebraic computation trees with integer inputs"want one, Proc. 30th Annual Symposium since we're on Foundations of Computer Science (FOCS 1989), pp. 308–313mathoverflow not stackoverflow). But these lower bounds don't apply to your problem because Probably the input simplest way is all integersjust to fill another array$H$with random numbers and let$h(x)=H[x]\$, but that is unacceptable because it uses too much space. I'll leave this part as unsolved and state this as a partial answer rather than claiming full rigor at this point.

Post Deleted by David Eppstein
1