samedi 11 juillet 2020

Nested loop time complexity (big-O) for algorithm

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