Dear Experts, Need solution in Java. The question is, for each function give the

Question

Dear Experts,

Need solution in Java. The question is, for each function give the best matching order of growth of the running time. Must show the workings on the answer. Thanks.

5 short questions:

Exercise: For each function, give the best matching order of growth of the running time.

1) public static int f1(int N) {

int x = 0;

for (int i = 0; i < N; i++)

x++;

return x;

}

2) public static int f2(int N) {

int x = 0;

for (int i = 0; i < N; i++)

for (int j = 0; j < i; j++)

x++;

return x;

}

3) int sum = 0;

for (int i = 1 i < N; i *= 2)

for (int j = 0; j < N; j++)

sum++;

4) public static int f4(int N) {

if (N == 0) return 0;

return f4(N/2) + f1(N) + f4(N/2);

}

5) public static int f7(int N) {

if (N == 1) return 0;

return 1 + f7(N/2);

}

Explanation / Answer

1. The running time for question 1 would be O(N).

Explanation : The first line is an assignment which gives O(1)

Second and third lines goes around the loop of lines n times, for a total of O(N)

Adding which O(1)+O(N), 1 being constant, O(N) is the time complexity for the given function

2.The running time for function 2 is O(N2).

Explanation: Here the inner loop is dependent on the outer loop and it executes for 1,2,3,4,...N times which makes in N2.

Consider that the x++ runs for 0+1+2+...+N-1 and the arithemtic sum for this will be N(N-1)/2 which is N2

O(1)+O(N)+O(N2) = O(N2)

3. The running time for function 3 is O(N2).

Explanation: Here the inner loop is not dependent on the outer loop and it executes for N times each time sum++ runs for N+N+N+......+N and the arithemtic sum for this will be N*N which is N2

The outer lopp runs for log N times;

O(1)+O(log N)+O(N2) = O(N2)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.