1. Consider the following two algorithms.

void algorithm1 (int [] a, int m) {

Random rand = new Random();

for (int i = 1; i <= m; i++){

int v = rand.nextInt();

sequentialSearch(a, v); //sequential search of value v in a[]

}

}

void algorithm2(int a[], int m){

quickSort(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[]

}

}

1. What is the worst-case complexity (in big O notation) of each of algorithm1 and algorithm2 in terms of n and m, where n = a.length and m is the given parameter? Assume rand.nextInt() is O(1). Justify the complexity.

Answer:

Algorithm	Complexity (in big O notation)	Why?
algorithm1
algorithm2

2. Which algorithm is faster and why?