Question

What are the valid runtime bounds for the method mystery with respect to argument n? Select all that apply.

public static int mystery(int n) {
    for (int i = 1; i < n; i = i + i) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < n; k++) {
                f0(n);
            }
        }
    }
    return -1;
}
public static void f0(int n) {
    int[] arr = new int[200];
    for (int i = 0; i < 200; i++) {
        arr[i] = i;
    }
}

Answer 1

Solution:

Explanation:

mystery function:

=>We can see in the function mystery(int n) there are three loops.

=>Outer for loop is independent loop and will run logn times from i = 1 to i < n doubling the value of i each time.

=>Middle for loop is dependent for loop which is depending upon outer for loop and will run from j = 0 to j < i incrementing the value of j by 1 each time.

=>Inner for loop is independent for loop and will run n times from k = 0 to k = n-1 incrementing the value of k by 1 each time.

=>After all loops f0(n) functions is called.

fo(n) function:

=>In f0 function there is only one for loop which is running 200 times from i = 0 to i = 199 incrementing the value of i by 1 each time.

=>Hence total number of times loop will be executed in f0 functions = 200 times.

=>Time complexity of f0 function = O(1)

Calculating overall time complexity:

=>Two for loops in mystery() function will be executed like: if i = 1 then middle loop will run only once, if i = 2 then middle loop will run twice, if i = 4 then middle loop will run 4 time and if i = 2^k where k is some constant then middle loop will run 2^k times.

=>Total number of time outer and middle loops will be executed = 1+ 2 + 4 + 8 + ... + 2^k where 2^k < n

=>Total number of time outer and middle loops will be executed = 1*(2^(k+1) - 1)

=>Total number of time outer and middle loops will be executed = 2*2^k - 1...(1)

=Let say 2^k = n (nearly equal)

=>k = log₂(n)...(1)

From (1) and (2)

=>Total number of time outer and middle loops will be executed = 2*2^log₂(n) - 1

=>Total number of time outer and middle loops will be executed = 2n - 1

=>Inner loop will run n times whenever it is executed so total number of times all loops will be executed = (2n-1)*n

=>Total number of times including f0 = (2n-1)*n*200

=>Time complexity = O(n^2)

I have explained each and every part with the help of statements attached to it.