I just learned about time and space complexity and I dont think I am really grasping them. I will put up some codes would would ask kindly if some of you could tell me their time and space complexity and how you decide them.
Code 1
public static int nmKomplex(int n, int m){
int sum = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j < m; i++)
sum += i * j;
return sum;
}
Code 2
public static void Schleife3(int n){
int sum = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j<= n; j++)
sum += i * j;
for(int i = 1; i <= n; i++)
sum += i
}
First code:
public static int nmKomplex(int n, int m){
int sum = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j < m; i++)
sum += i * j;
return sum;
}
TL:DR Time Complexity O(n * m)
| Space Complexity O(1)
A loop that goes from i = 1
to n
times another loop that goes from j=1
to m
. For n > 1
, the first loop performs (n - 1)
iterations, times the second loop which performs (m - 1)
iterations. Hence, the double loop executes nm - n - m + 1
iterations, which can be represented by a time complexity of O(n * m)
.
The space complexity is O(1)
(i.e., constant) since an increase in either the n
and m
values does not reflect in an increase of the space used.
Second code:
public static void Schleife3(int n){
int sum = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j<= n; j++)
sum += i * j;
for(int i = 1; i <= n; i++)
sum += i
}
TL:DR Time Complexity O(n^2)
| Space Complexity O(1)
For n > 1, the first loop performance n
iterations times the second loop which also performances n
iterations plus the third loop which also performance n
iterations. Therefore, time complexity of n^2 + n, which can be represented by O(n^2)
.
The space complexity is O(1)
(i.e., constant) since an increase in either the input n
does not reflect in an increase of the space used.