I'm having a hard time understanding algorithm analysis, especially the following example:
for (int i = 1; i < n^3; i = 2*i){
for (int j = 6*n; j > 0; j = j-2){
}
}
So my understanding of this is that the outer loop is O(nlogn) as i is multiplied by a constant amount, I'm unsure if the n^3 makes any difference or not.
The inner loop confuses me the most though. I think it's O(n) as j is decremented by a constant amount but I'm uncertain whether the 6*n and the j > 0 have any influence.
If i'm correct then this entire algorithm would be O(nlogn)? Uncertain how to express the time complexity T(n) of this though.
Any insights would be hugely appreciated.
The outer loop is not O(nlogn) - since i is multiplied in 2 every loop, it goes: 2, 4, 8, 16, 32... this means that it will take a log(n^3) steps for i to reach n^3 (the base of the log is 2).
More formal: O(log(n^3)) = O(3logn) = O(logn)
In the inner loop j is initialized to 6*n and goes down in steps of 2. This means that it'll take 6n/2 steps for j to reach zero.
More formal: O(6n/2) = O(3n) = O(n)
So the complexity of the code section is O(n) * O(logn) = O(nlogn)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments