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; }
Question
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; }
Solution
The time complexity of the given code is O(N^2) for the first nested loop and O(N) for the second loop. So, the overall time complexity is O(N^2 + N), which simplifies to O(N^2) because we only consider the highest order term for large inputs of N.
The space complexity of the given code is O(1), which means it uses constant space. This is because the code only uses a fixed amount of space to store variables and does not use any data structures that grow with the size of the input.
Similar Questions
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 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? 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)
What is the time, space complexity of following code : int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); }Assume that rand() is O(1) time, O(1) space function.
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++; } }
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.