Java Question:

Write code to fill an array of size n with unique random numbers in the range 0-10n (inclusive). Write one method that is

O( n ).

Recall that often a more efficient solution will require more memory!

You can use the driver program to test your code. I recommend testing with a small array first to make sure your code works properly (perhaps n = 10). I also recommend first testing with random numbers in the range of 0-n, to make sure your code really works to select uniquenumbers.

Then, you can increase the size to compare the running time. (I start to notice a difference at n = 10000!) (Hint: comment out the line that prints the array once you start using such big arrays!) Note the time for the linear and quadratic algortihms when n=10000. Then double the size to n=20000. You should notice that the linear running time also roughly doubles, while the quadratic running time roughly increases by 4x!