What is the time complexity of the following code? for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { System.out.println(i * j); } } a. O(n) b. O(2^n) c. O(n^2) d. O(n log n)
Question
What is the time complexity of the following code? for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { System.out.println(i * j); } }
a. O(n)
b. O(2^n)
c. O(n^2)
d. O(n log n)
Solution
The time complexity of the given code is O(n^2). This is because there are two nested loops in the code. The outer loop runs n times and for each iteration of the outer loop, the inner loop runs i times. Therefore, in the worst-case scenario, the inner loop runs n times for each iteration of the outer loop, resulting in a time complexity of O(n^2). So, the correct answer is c. O(n^2).
Similar Questions
What is the time complexity of the following code :int i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n/2; }}
What is the time complexity of the following code : int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } }
What is the time complexity of this function / algorithm?void f(int n){ int i; int j; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { printf("[%d] [%d]\n", i, j); } }}O(n)O(1)O(log(n))O(nlog(n))O(2^n)O(n!)O(n^2)
Q2(b) What will be the time complexity of the following? Give proper explanation. for (int j = 4; j<n; j=j+2) { val = 0; for (int i = 0; i<j; ++i) { val = val + i* j; for (int k = 0; k < n; ++k) val++; } }
What is the time, space complexity of following code :int a = 0, b = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { a = a + j; } } for (k = 0; k < N; k++) { b = b + k; }
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.