0

So assume we are given an array of m numbers, the max number in this array is k. There are duplicates in this array.

let array a = [1,2,3,1,2,5,1,2,3,4]

Is there an algorithm that prints out this array after o(n) operation result in [1,2,3,4,5](both sorted and no duplicate), where n is the quantity of unique values.

We are allowed to use k memory -- 5 in this case. The algorithm I have in mind is to use a hash table. Insert value into a hash table, if the value exist before, we ignore it. This will sort automatically. However, if we have 5 number, [1,2,3,100,4] but one of them is 100, means when printing these 5 numbers, we need to run o(k) ~= 100 time instead of o(n) ~= 5 time. Is there a way to solve this problem?

Gerry G
  • 48
  • 5
  • Hi - welcome to Stack Overflow. Could you format your quesiton properly with line breaks and code blocks? – dwjohnston Nov 29 '18 at 23:04
  • 3
    You have defined `n` both as the size of the original input, and the quantity of unique values. Please disambiguate. – Prune Nov 30 '18 at 00:26
  • It seems that your approach requires a perfect hash function -- or a custom hash function, at the very least. How do you generate that function in **O(n)** time? – Prune Nov 30 '18 at 00:27
  • 1
    What is n? You defined it twice in conflicting ways. – Matt Timmermans Nov 30 '18 at 01:28
  • 1
    This is doable if you don't have to sort the output, and you are allowed to use uninitialised values. But I don't know of a way to do it in O(n) with sorted output. – rici Nov 30 '18 at 03:37
  • Thank you so much for the help! It is a lovely community! Loved it! – Gerry G Nov 30 '18 at 05:27

2 Answers2

0

You suggest that printing 5 numbers takes o(k) (or 100) time instead of o(n). That is wrong because, to print those 5 numbers, it takes 5 time to iterate and print. How would the value of your number change the time in which it takes to pull off this problem? The only situation when that should make a difference is if the value is greater than the allowable value in a 32-bit integer, or 2^32-1. Then you would have to detect those cases and treat them differently. However, assuming you don't have any integers of that size, you should be able to print 5 integers in O(5) time. I would go back over your calculation of the time it takes to go through your algorithm.

With your method, if you're using efficient algorithms, you should be able to remove duplicates in O(n log n) time, as seen here.

The way I see it, if you have a piece of the algorithm (the hashing part, where you remove duplicates and sort) running in O(n log n) time, and a piece of the algorithm (printing the array) running O(N) (or O(5) in this case), the entire algorithm runs in O(N) time: O(N) + O(N log N) -> O(N), since O(N) >= O(N log N). I hope that answers what you were asking for!

Looks like I was wrong, since O(N log N) of course grows faster than O(N). I don't think there's any way to pull off your problem.

Adam
  • 39
  • 1
  • 9
  • O(N log N) grows faster than O(N), not the other way round, so the entire algorithm would be O(N log N), not O(N). – Ergwun Nov 30 '18 at 01:31
  • @Ergwun good point. That was the only way I could think of to make it work, so In guess it makes sense that I was incorrect – Adam Nov 30 '18 at 03:18
  • Thanks so much for the help! The reason I said o(k) time to print is because it took o(n) to insert on the hash table, and took o(k) to loop over hash table to print. I guess there is not a way after all, thank you anyways! – Gerry G Nov 30 '18 at 05:24
0

I don't think there exists such algorithm. Take a look here https://en.wikipedia.org/wiki/Sorting_algorithm

Essentially for comparison based algorithms the best you can achieve is O(nlogn). But since you have provided the max value k I would assume you want something more than just comparison based algorithm.

But for non-comparison based algorithms, since it by nature depends on magnitude of the numbers, the complexity has to reflect such dependency - meaning you will definitely have k somewhere in your total time complexity. You won't be able to find an algorithm of just O(n).

Conversly, if that O(n) algorithm were to exist and were not to depend on k. You can sort any array of n numbers since k is an extra, useless information.

Vince
  • 81
  • 4