Algorithm Complexity – For loop inside while loop; decreasing by factor 2

algorithmscomputational complexity

Question: What is the "correct" way to interpret the algorithm described below?

I wanted to check if my understanding of the below algorithm is correct, as I haven't "encountered" this scenario where the inner for loop, I think, is affected by the value of $m$ being constantly halved. If it helps, indices run from 1 to $n$, and the input is an integer array, and a size $n$.

function F(A[.],n)
    s <- 0
    m <- n
    while m > 0
        for i <- 1 to m do
            s <- s + A[i]
        m <- m/2

My understanding is we look at the inner most loop first, which is the for loop. Therefore, it is in $O(m)$ complexity, as it iterates up to $m$. Looking outside of this loop, is the while loop, which starts at $n$ but it constantly halved, meaning it's in $O(logn)$ complexity. Therefore, overall complexity is $O(mlogn)$.

However, what is "tripping me up" is because $m$ is being halved, that would be affecting the inner for loop, which would then mean it traverses the Array "half" the time, therefore be $O(logn)$ complexity. As before, the outer while loop is $O(logn)$, therefore overall complexity is $O(logn*logn)$.

How should I be "analysing" this algorithm, as I feel like the two answers are "viable" but the bottom one makes the most "sense.

Best Answer

HINT

You summary complexity is (assuming $n=2^p$) $$ \sum_{k=1}^p \left(3\cdot 2^k +1\right) $$

Can you sum the geometric series and convert the result to $n$?

UPDATE

To answer your question in the comments, every iteration of the inner for-loop is 3 operations: A[i] value lookup, s += A[i] and i += 1 (loop index increment). I am assuming += to be atomic, i.e. counting as one operation, if in reality you are implementing assignment and addition separately, it will be 2 operations each, hence 5 operations total.

Finally an iteration of the outer loop needs m /= 2 with the check m > 0, which I am also assuming is atomic. If not, you would need 3 operations here, and the entire loop would be $5 \cdot 2^k+3$ instead.

Related Question