Java Question: Write code to fill an array of size n with unique random numbers

Question

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(n2) or worse

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!

Explanation / Answer

//comment out print statement in for loop when running for n = 10000 and n=20000

import java.util.Random;
import java.util.Formatter;
import java.util.Locale;

public class MyClass {
public static void main(String args[]) {
//change the array size here inside int[] bracket to required size
int []arr =new int[20000];

Random r = new Random();
int Low = 0;
int High = arr.length *10;
long start = System.currentTimeMillis();
for(int i = 0; i < arr.length; i++)
{
arr[i] = r.nextInt(High)+Low;

//uncommnt when n is small number, comment for n =10000 and n= 20000
//if(i%10 == 0)

  //uncommnt when n is small number, comment for n =10000 and n= 20000
// System.out.printf(" ");

  //uncommnt whn n is small number, comment for n =10000 and n= 20000
//System.out.printf("%d " , arr[i]);
}
long end = System.currentTimeMillis();
System.out.printf(" start = %d " ,start );
System.out.printf(" end = %d " ,end );
System.out.printf(" duration = %d " ,end-start );
long diff = end -start;
float duration = (float)diff/1000;
System.out.printf(" Execution time is %1.5f seconds" ,duration );
}
}

-----------------------------------------------------------------------------

when n = 10,output

36 72 13 7 87 44 64 88 30 60
start = 1507010426369

end = 1507010426382

duration = 13

Execution time is 0.01300 seconds

//when n =20

160 116 70 100 154 195 123 197 140 191 4 107 77 146 128 163 178 170 80 117
start = 1507010488076

end = 1507010488093

duration = 17

Execution time is 0.01700 seconds

//when n =100

229 446 390 978 174 987 897 619 133 524
246 877 91 897 746 823 459 531 392 210
184 475 578 189 894 340 383 542 709 215
792 487 424 139 189 579 444 735 413 796
404 654 658 626 713 974 995 977 302 853
563 616 593 912 118 633 566 673 972 122
166 836 110 711 28 150 782 818 248 187
107 9 661 259 633 881 917 671 103 524
92 406 546 877 849 519 799 140 665 426
614 146 942 399 58 770 749 506 637 826
start = 1507010673959

end = 1507010673990

duration = 31

Execution time is 0.03100 seconds

---------------------------------------

//whn n=10000

start = 1507010994871

end = 1507010994874

duration = 3

Execution time is 0.00300 seconds

-------------------------------------------

//n =20000

start = 1507011043612

end = 1507011043618

duration = 6

Execution time is 0.00600 seconds

-------------------------------------

you can notice linear time double when n=20000 ie

when n=20000 , time is 0.003

when n=20000 tim = 0.006

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.