Determine how many times the output statement is displayed in each of the follow

Question

Determine how many times the output statement is displayed in each of the following fragments. Indicate whether the algorithm is O(n) or O(n2).

a. for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) System.out.println(i + " " + j);

b. for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) System.out.println(i + " " + j);

c. for (int i = 0; i < n; i++) for (int j = n - 1; j >= i; j--) System.out.println(i + " " + j);

d. for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) if (j % i == 0) System.out.println(i + " " + j);

Explanation / Answer

a) O(n^2) number of times statement op = n^2

b) O(n) number of times statement op = 2n

c)O(n^2) number of times statement op = 1+2+3+4+...+n = n*(n+1)/2

d)O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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