Question

Array manipulation (a) Write Java code for a method exchange (int [] a, int i, int j) that exchanges the values stored at indices i and j in the array a. You do not need to worry about cases where either i or j is an invalid index. Give the best estimate you can for its time complexity (b) In an ordered array of n items, how can we determine whether or not an item belongs to the list using only O(log n) comparisons? int hi) that sums (c) Write Java code for a method sum (int [] a, int lo, the values stored at indices between 10 (inclusive) and hi (exclusive) in the ar- ray a. You do not need to worry about cases where either lo or hi is an invalid index, but the method should return 0 if hi <= lo. Give the best estimate you can for its worst-case time complexity (d) Suppose that we want to construct an array b of the same size as a with the prop erty that b[i sum (a,0,i+1). One approach would be to use a . length different calls to the sum method of the previous problem. What would the time complexity of that approach be? Come up with a better approach of complexity O(n) where n is the length of a. You need only describe this second approach in words, though code is fine too. (e) Assuming we have the array b from the previous part of this question, how could sum (int [ a, int lo, int hi) be determined in constant, i.e., O(1) time?

Answer 1

Below, I have attached the codes for the given problems.

(a)

public void exchange(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

The worst case time complexity will O(1).

(b)

Using binary search we can determine whether an present or not using (log n) comparisons. Binary search will make two equal halves repeatedly until the middle element every time is equal to the required element.

(c)

public int sum(int[] a, int lo, int hi){
int sum=0;
for(int i=lo; i<hi; i++){
sum = sum + a[i];
}
return sum;
}

(d)

Here is the other approach where time complexity is O(n). The main logic here is, we compute sum till present ith index and just copy that sum at every iteration.

public int createB(int[] a,int[] b, int lo, int hi){
int sum=0;
for(int i=lo; i<hi; i++){
sum = sum + a[i];
b[i] = sum;
}
return sum;
}

(e)

If we had an array b which was derived from array a, and we need to compute sum(a, lo, hi) in O(1) time is as follows:

sum = b[hi-1] - b[lo - 1]

Hoping that the solutions helps. Please comment for further assistance.