Very hard sorting algorithm problem - O(n) time - Time complextiy?

By assuming multiplication and division is O(1).

By assuming multiplication and division is O(1): Think about numbers, you can write them as: Number(i) = A0 * n^765 + A1 * n^764 + .... + A764 * n + A765. For coding number to this format, you should just do Number / n^i, Number % n^i, if you precompute, n^1, n^2, n^3, ... it can be done in O(n * 765)=> O(n) for all numbers. Precomputation of n^i, can be done in O(i) since I at most is 765 it's O(1) for all items.

Now you can write Numbers(i) as array: Nembers(i) = (A0, A1, ..., A765) and know you can radix sort items : first compare all A765, then ...., All of Ai's are in the range 0..n so for comparing Ai's you can use Counting sort (Counting sort is O(n)), so your radix sort is O(n * 765) which is O(n). After radix sort you have two sorted array and you can simply find one similar item in O(n) or use merge algorithm (like merge sort) to find most possible similarity (not just one). For generalization if the size of input items is O(n^C) it can be sorted in O(n) (C is fix number).

But because the overhead of this way of sortings are big, prefer to using quicksort and similar algorithms. Simple sample of this question can be found in Introduction to Algorithm book, which asks if the numbers are in range (0..n^2) how to sort them in O(n). Edit: for clarifying how you can find similar items in 2-sorted lists: You have 2 sorted list, for example in merge sort how do you can merge two sorted list to one list?

You will move from start of list 1, and list 2, and move your head pointer of list1 while head(list(1)) > head(list(2)), and after that do this for list2 and ..., so if there is a similar item your algorithm will stop (before reach the end of lists), or in the end of two lists your algorithm will stop. It's as easy as bellow: public int FindSimilarityInSortedLists(List list1, List list2) { int I = 0; int j = 0; while (i Count) { if (list1i == list2j) return list1i; if (list1i.

This is the most logical answer. But numbers are not power of n. Numbers are between 0 and n^765.

For example a number can be n^765-1 or n^454-66 . At first I also thought similiar way to yours . But since numbers are not always power of n it fails.

– MonsterMMORPG Dec 17 '10 at 22:13 @PokemonCraft, I didn't said that numbers are pow of n I said you can write each number in "A0 * n^765 + A1 * n^764 + .... + A764 * n + A765" format, for example for n^765 -1 you have : A0 = 1, A765 = -1, Ai = 0 for others, or for n^454-66 you have A310 = 1, A0 = -66, Ai = 0 for others. – Saeed Amiri Dec 18 '10 at 6:08 I did not understand how will I check whether they contain same value or not after sorting the way you suggested without increasing O(n) time complexity. – MonsterMMORPG Dec 20 '10 at 11:43 @PokemonCraft, I'd updated my answer.

– Saeed Amiri Dec 21 '10 at 5:54.

What you want is impossible. Each element will be stored in up to log(n^765) bits, which is O(log n). So simply reading the contents of both arrays will take O(n*logn).

If you have a constant upper bound on the value of each element, You can solve this in O(n) average time by storing the elements of one array in a hash table, and then checking if the elements of the other array are contained in it. Edit: The solution you may be looking for is to use radix sort to sort your data, after which you can easily check for duplicate elements. You would look at your numbers in base n, and do 765 passes over your data.

Each pass would use a bucket sort or counting sort to sort by a single digit (in base n). This process would take O(n) time in the worst case (assuming a constant upper bound on element size). Note that I doubt anyone would ever choose this over a hash table in practice.

It can be done with hashing method but I also need to have that hashing method. Not just saying using hashing. So I have to explain what kind of hashing is used.

– MonsterMMORPG Dec 17 '10 at 12:40 do not care about bit size. I need the logic. – MonsterMMORPG Dec 17 '10 at 12:45 @PokemonCraft: You can use pretty much any kind of hash table you want.

Its size should be around 2*n. To save space, you can store pointers to the values in the hash table instead of the values themselves. – interjay Dec 17 '10 at 13:11 2 As for your second comment: maybe you don't care about bit size, but bit size means that O(n) is impossible for the problem you described.

– interjay Dec 17 '10 at 13:13 @interjay, as you wrote in your first paragraph every iteration on a list of numbers within 0..n of size n takes O(nlog(n)), you changed the world :) so finding max item in the list of size n, and numbers within 0..n is O(nlog(n)) :) (n^765 can be coded in 765log(n) and n can be coded in log(n)), the main part of your false conclusion is there is no need to iterate over all bits. Comparing items takes O(1) – Saeed Amiri Dec 17 '10 at 15:56.

If memory was unlimited you could simply create a hashtable with the integers as keys and the values the number of times they are found. Then to do your "fast" look up you simple query for an integer, discover if its contained within the hash table, and if found check that the value is 1 or 2. That would take O(n) to load and O(1) to query.

Yes but unfortunately I do not have unlimited memory. – MonsterMMORPG Dec 17 '10 at 12:41 @PokemonCraft: what are exactly your memory limitations? Certainly you can use O(n) memory, no?

– R. Martinho Fernandes Dec 17 '10 at 12:46 well actually there are no memory limitations. But the array size can not be biggest number in the given arrays .

For example let the biggest number is 76^534 . The array size that we are going to use can not be equal to this number. Because there are so many O(n) sorting algorithms with this way working.

– MonsterMMORPG Dec 17 '10 at 12:49 @PokemonCraft hashtables don't need to have space every possible item, just enough space so that items don't collide very often. A hash table of size 2-3 times bigger than n should be more than sufficient and still far less than n^765. – MerickOWA Dec 17 '10 at 16:05 1 @PokemonCraft I don't completely understand your comment but... What I'm saying is that the input, i.e.

The list of numbers, must be static in nature to guarantee that you're never going to get a collision. Otherwise it's impossible to guarantee that you're never going to be a collision. – wheaties Dec 17 '107 at 3:29.

I do not think you can do it O(n). You should check n values whether they are in the other array. This means you have n comparing operations at least if the other array has just 1 element.

But as you have n element it the other array as well, you can do it just O(n*n).

You can do membership checks in ~O(1) time. Look up hash tables. – R.

Martinho Fernandes Dec 17 '10 at 12:35 well you can do it with O(n) time complexity for sure since it is asked from me to achive this. Also hash table is a good way but what kind of hash algorithm I can use. I have to also have an idea about hash algorithm .

Because it is also asked. Hash algorithm for sure would solve the problem but it can not be a black box :) – MonsterMMORPG Dec 17 '10 at 12:38 @Pokemon: "well you can do it with O(n) time complexity for sure since it is asked from me to achive this" Your reasoning is deeply flawed here. You are fortunate not having had the experience of dealing with professors who have zero clue what they are talking about.

– Mehrdad Afshari Dec 17 '10 at 12:41 Do not forget the cost of building a hash table – Zoltan Hamori Dec 17 '10 at 12:43 @ Mehrdad Afshari maybe it is unfortunate that you can not solve this kind of problem ^^. Well this is possible with O(n) time complexity without having biggest number sized array. And I have to figure it out :) – MonsterMMORPG Dec 17 '10 at 12:47.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.