How to prove an algorithm is Θ (log n) using summation notation?

Question

Suppose I have the following code:

int sum = 0;
int val=128;
for (int i=n; i>=1; i=i/2) {
    for (int j=1; j<val; j++) {
    sum ++;
    }
}

How would you prove this to be Θ(log n) mathematically?

My usual approach would be to use summation (sigma notation), but in this case we are not increasing the loop variable linearly. What is a good approach for this?

Answer 1

The values of i are n, n/2, n/4, ..., 1. Since it's integer its final value is 1 with this condition. Assume n to be 2^k, then the number of iterations would be k, which is log n. Therefore the situation does not change, it is another for with certain number of iterations.

The inner loop can be considered a single statement, because val is constant.