Please help. For each method below, determine the order of growth of the worst c
ID: 649368 • Letter: P
Question
Please help. For each method below, determine the order of growth of the worst case running time as N increases. Write the answer using big-O notation.
a) public static double f1(double [][] array) {
int N = array[0].length;
double b = Math.random();
for (int i = 0; i < 3; i++)
for (int j = n-1; j >0; j--)
b *= n*n*array[i][j];
}
b) public static int f2(int[] arr){
//n is arr.length, n>>50
int count = arr.length-1;
while(count > 0) {
if (arr[count] < 0)
count -= 7;
count = count - arr.length/50;
}
return count;
}
c) public static boolean f3(double [][] array) {
//n is array.length
for (int i = 0; i < array.length, i++)
for (int j = 0; j < i; j++)
if (array[i][j] == 0)
return true;
return false;
}
d) public boolean f4(int [] arr, int lo, int hi) {
// n = initial value of (hi-lo+1) of 1st activation of f4
if (lo == hi)
return false;
if (arr[i] * arr[lo] > 10)
return true
return f4(arr, lo+1, hi)
}
e) public int f5(int [] array, int x) {
// n = array.length
int m = array.length-1;
while (array[m] > x && m > 0)
m = m/2;
return m;
}
Explanation / Answer
a)
The outer loop is executed for 3 times. Therefore its complexity is O(3).
The inner loop is executed for (n-1) times. Therefore its complexity is O(n-1).
The total complexity is O(3*(n-1)) = O(3n-3) = O(n).
b)
Assume that the array contains positive numbers only. Then the while loop is executed for count times.
Therefore, the complexity is O(n).
c)
The outer loop executes n times. Where n is the length of the array.
Therefore, its complexity is O(n)
The inner loop execution is depends on the value of i.
For i=0, the inner loop executes 0 times
For i=1, the inner loop executes 1 times
For i=2, the inner loop executes 2 times
For i=3, the inner loop executes 3 times
For i=n, the inner loop executes n time
Therefore, its complexity is also O(n)
The total complexity is O(n*n) = O(n2).
e)
In worst case, any one of the condition may fail for each element in the array.
Then the while loop is executed for n-1 times where n is the length of the array.
Therefore, the complexity is O(n).