Identify the space and time complexity of the following chunks of code. I will post the answers later
- Simple loop
int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); }
Select here to see the answer: Time: O(N+M), Space: O(1)
- Nested loop
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; }
Select here to see the answer: Time: O(N2), Space: O(1)
- Another nested loop
int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } }
Select here to see the answer: Time: O(N2), Space: O(1)
Let me know if you need explanation for the answers 🙂