Dear Experts, Got 5 short question in Java. pls solve. Thanks. For each function

Question

Dear Experts,

Got 5 short question in Java. pls solve. 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

Order of segment of code depends upon the number of times For or While loop runs
1) Loop runs N times so order is O(N);
2) For each outer loop inner loop runs N times and outer loop run N times so is of O(N^2);
3) For each outer loop inner loop runs N times and outer loop runs log(N) times so is of O(N*log(N)). (2^0, 2^1, ..2^logN) each outer loop i's value.
4) f4(N)=N +2*f4(N/2)
       => N + 2*N/2 +2*2*f4(N/4)
       => N + N + .... log(N) times
       => N*logN
   so order is N*logN
5)f7(N)=1+f7(N/2)
       =>1+ 1+ ... log(N) times
so order is log(N);

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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