Maybe a bit of a silly question but the run time analysis for this code is confusing me.
int i, j;
int k = 0;
for(i = 1; i<= n; i*= 2){
for (j = 1; j <= i; j++){
k += (i+j);
}
}
I understand that the outer loops runtime would be log(base2)n and that the overall value of the runtime is the runtime of the outer loop * the runtime of the inner loop. I'm just a little confused about the inner loop, I know the inner loop is iterating based on the value of i.
So would the inner loops runtime also be log(base2)n and then the overall runtime would be (log(base2)n)^2?
Somehow I don't feel like that's right.
The complexity in this case is determined by the number of times the inner loop will execute, multiplied by the complexity of body of the inner loop.
Regarding the number of times it will execute:
The outer loop will have the values 1,2,4,8,...,n.
In each of the outer loop iterations the inner loop will execute times according to this value.
Therefore altogether the inner loop will execute:
1+2+4+8+...+n.
This is a geometric series with a (first element) of 1, r (factor) of 2, and containing log(n) elements.
The formula for the sum of m elements of a geometric series is (r != 1):
Sm = a * (1 - r ^ (m+1)) / (1 - r)
If we assign a=1, r=2, m=log(n) we get:
1 * (1 - 2 ^ (logn+1)) / (1-2) =
1 * (1 - 2 * 2 ^ logn) / (1-2) =
1 * (1 - 2n)) / (-1) =
1 * (2n - 1) =
2*n - 1
=>
O(n)
In this specific case you can also see it as the value of a binary value of logn bits, all set to 1, which is again 2*n - 1 => O(n).
Regarding the body of the inner loop:
It contains a constant amount of calculations and so it is O(1).
=> Therefore the overall complexity is O(n) * O(1) = O(n).
Note:
This assumes that we are dealing with limited size integers (e.g. 64 bit), which is what types like int that you used usually are. If you want to include the analysis for arbitrary large integers up to n, representing and doing operations like addition (which you used) on them becomes O(logn) instead of O(1).