Dear Experts, i resend the questios because in need the explanation for the answ

Question

Dear Experts,

i resend the questios because in need the explanation for the answer for each question.

Got 5 short question in Java. pls solve and MUST provide explanation. Thanks.

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 function takes one argument n and uses loop from 0 to n and increments x each time so the final value in x will be n and its complexity will be O(n) because there is only 1 loop which goes from 0 to n so the loop runs only n times.

2. Second function uses two nested loops . First loop goes from 0 to n and the inner for loop goes upto i times for every iteration of outer loop . So for example it value in n is 2 then outer loop will run 2 times (for 0 and 1) and inner loop will run only once when i=1 and j=0. So the the complexity will never exceed O(n^2)

3. In third function the outer loop runs only n/2 times because i gets doubled on each iteration. The inner loop executes n times for each iteration for outer loop. Thus the total complexity will be O(nlogn)

4. Third function uses three recursive calls so the complexity will be O(n/2 + n + n/2) So the final complexity will be O(n)

5. Fifth function uses one recursive call f7(n/2) Thus its complexity will be logn

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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