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.
Question
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.
Solution
The time complexity of the given code is O(N+M). This is because there are two separate loops in the code. The first loop runs N times and the second loop runs M times. Since these loops are not nested, we add the complexities, resulting in O(N+M).
The space complexity of the given code is O(1). This is because the amount of space does not change with the size of the input, it remains constant. Only two integer variables 'a' and 'b' are used, which take constant space. The rand() function also takes constant space. Therefore, the space complexity is O(1).
Similar Questions
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; }
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 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 will be the time complexity of the following code?int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2){ for (int j = 0; j < i; j++){ count += 1;| } }return count;
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
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.