void algorithml (int a[], int m) { selectionSort(a, 0, a.length-1); //quick sort of array a[] for...

  

Transcribed Image Text:

void algorithml (int a[], int m) { selectionSort(a, 0, a.length-1); //quick sort of array a[] for (int i = 1; i <= m; i++) { int v = rand.nextInt (); binarySearch(a, v); // binary search of value v in array a [] } Consider the following two algorithms. } void algorithm2 (int [] a, int m) { Random rand = new Random(); for (int i = 1; i <= m; i = 2*i) { int v = rand.nextInt (); } wwwwww. sequentialSearch (a, v); //sequential search of value v in a [] } (a) (3 points) What is the worst case complexity (in big O notation) of each of algorithml and algorithm2 in terms of n and m, where n = a.length a . length and m is the given parameter? Assume rand.next Int () is O(1). Justify the complexity. Activate Windo Answer: Algorithm algorithm1l algorithm2 Complexity (in big O notation) (b) (2 points) Which algorithm is faster and why? Answer: Why? void algorithml (int a[], int m) { selectionSort(a, 0, a.length-1); //quick sort of array a[] for (int i = 1; i <= m; i++) { int v = rand.nextInt (); binarySearch(a, v); // binary search of value v in array a [] } Consider the following two algorithms. } void algorithm2 (int [] a, int m) { Random rand = new Random(); for (int i = 1; i <= m; i = 2*i) { int v = rand.nextInt (); } wwwwww. sequentialSearch (a, v); //sequential search of value v in a [] } (a) (3 points) What is the worst case complexity (in big O notation) of each of algorithml and algorithm2 in terms of n and m, where n = a.length a . length and m is the given parameter? Assume rand.next Int () is O(1). Justify the complexity. Activate Windo Answer: Algorithm algorithm1l algorithm2 Complexity (in big O notation) (b) (2 points) Which algorithm is faster and why? Answer: Why?

Answer rating: 100% (QA)

Answer Lets analyze the worstcase complexities of a... View the full answer