Part 1: public static void displayArray(int array[], int first, int last) { if (
ID: 3746356 • Letter: P
Question
Part 1:
public static void displayArray(int array[], int first, int last) {
if (first == last) System.out.print(array[first] + " ");
else {
int mid = (first + last) / 2; displayArray(array, first, mid); displayArray(array, mid + 1, last);
} // end if } // end displayArray
Suppose that the array’s middle element is not in either half of the array. Instead you can recursively display the left half, display the middle element, and then recursively display the right half. What is the implementation of displayArray if you make these changes?
Part 2:
Implement the changed array in Java pseudocode and then analyze the algorithm in Big-Oh notation.
Explanation / Answer
The displayArray function is implemented as follows:
public static void displayArray(int array[], int first, int last) {
if(first<=last){
int mid = (first+last)/2;
displayArray(array, first, mid-1); //recursively display left half
System.out.print(array[mid]+" "); //display middle element
displayArray(array, mid + 1, last); //recursively display right half
}
}
Test code for testing the above function is :
public class HelloWorld{
public static void main(String []args){
int arr[] = {1,2,3,4,5};
displayArray(arr,0,4);
}
public static void displayArray(int array[], int first, int last) {
if(first<=last){
int mid = (first+last)/2;
displayArray(array, first, mid-1); //recursively display left half
System.out.print(array[mid]+" "); //display middle element
displayArray(array, mid + 1, last); //recursively display right half
}
}
}
OUTPUT:
The above algorithm visits each element if the array once and prints it. Thus it has time complexity of O(n).