I have created a simple program and I am now task to finding the time complexity (big-O). Below is the code:
if(B <= A) {
...
for(int i = 0; i < A; i++) {
...
}
for(int i = 0; i < B; i++) {
...
if(input >= 1)
validate = true;
else
validate = false;
for(int i = 0; i < B; i++) {
...
for(int k = i+1; k < B; k++) {
...
}
}
if(validate == true) {
...
for(int i = 0; i < B; i++)
...
}
else {
...
}
}
else {
...
}
This is my attempt to the problem:
'if' can either be 0 or 1, therefore assigned 'b'
1st 'for loop' is n
2nd 'for loop' is n
'if' inside the 2nd 'for loop' is n, since it will run n time depending on the 2nd for loop
3rd 'for loop' is n
4th 'for loop' is m, since it is nested for loop inside 3rd 'for loop'
'if' can either be 0 or 1, therefore assigned 'c'
5th 'for loop' is n
Therefore:
b + n + n + n + (n * m) + c + n
= 4n + nm + b + c
= O(nm)
I am confused on how to calculate time complexity when nested loops are involve (I am new to algorithm). Is my approach partially correct, or it is completely wrong? How should I approach such a time complexity problem for such a simple algorithm?
Lastly, if one of the above nested for loop becomes a 'while' loop, what will happen to the time complexity calculation then?
Aucun commentaire:
Enregistrer un commentaire