Space Complexity explanation


Space Complexity is O(1) only because a and b are replaced in memory and not taking new memory!


Let rand() be a black box. They have told us space complexity of rand() is O(1). So when it is called and when it return to main the Activation Record for rand() is removed and again the same thing happens. The concept for a and b is already told by sachin_yadav_365.


variable a and b are constants. Both loops are doing some processing and storing the values to a or b. which is constant… so the bigOh is constant storage. so we denote constant storage as bogOh(1).

In the same way, if both loops are considering new variable to store values at each loop pass then it would be directly proportional to the number of elements in the array. Means If loop will run to 10 times then 10 storage would be needed. If loop will run to 1000 times then 1000 storage would be needed. It means bigOh in that case could be bigOh(N)


amount of memory consumed while running the program


In this question there are two loops running.
First loop is

 for (i = 0; i < N; i++) {
            a = a + rand();  
```here i executes N times(0 to N-1) so it's complexity is o(n)
And second loop is 

for (j = 0; j < M; j++) {
b = b + rand();

Actually both loops are independent(not nested) so to find total time complexity of program we add both time complexity : o(N) + o(M)
Using asymptotic notation it become O(N+M).