I know that every for loop is a O(log₂n), but I am not sure what 3 of them together would make? O(3⋅log₂n)? Thank you guys.
for (int i = n; i > 0; i = i / 2) {
for (int j = n; j > 0; j = j / 2) {
for (int k = n; k > 0; k = k / 2) {
count++;
}
}
}
Each loop for it self has the time complexity Θ(log₂n), as you say.
Since the loops does not depend on each other, i.e. the variables i, j and k have no effect on each other, The complexity of the three nested loops can simply multiplied and you get Θ((log₂n)⋅(log₂n)⋅(log₂n)) = Θ((log₂n)³), also written as Θ(log₂³n). This means it is also in O(log₂³n).
Notice: You can not simplify log₂³n to 3⋅log₂n since log₂³n is not equal to log₂n³.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments