Java

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(n2) or worse and one 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 unique numbers.

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!

Part 1

Write O( n ) code to fill the array.

Hints:

Recall that often a more efficient solution will use more memory. Can you use another array or an array of another type to help you create a more efficient solution?

Only nested loops result in O(n2) efficiency. Consecutive loops can still be O( n ).

Part 2

Write O(n2) code to fill the array.