Complejidad del algoritmo - Bucle For dentro del bucle while; disminuyendo por el factor 2

Question

Pregunta: ¿Cuál es la forma "correcta" de interpretar el algoritmo descrito a continuación?

Quería comprobar si mi comprensión del siguiente algoritmo es correcta, ya que no me he "encontrado" con este escenario en el que el bucle for interno, creo, se ve afectado por el valor de $m$ siendo constantemente reducido a la mitad. Si ayuda, los índices van de 1 a $n$ y la entrada es una matriz de enteros, y un tamaño $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

Según tengo entendido, primero miramos el bucle más interno, que es el bucle for. Por lo tanto, es en $O(m)$ complejidad, ya que itera hasta $m$ . Mirando fuera de este bucle, está el bucle while, que comienza en $n$ pero se redujo constantemente a la mitad, lo que significa que está en $O(logn)$ complejidad. Por lo tanto, la complejidad global es $O(mlogn)$ .

Sin embargo, lo que me hace "tropezar" es que $m$ se está reduciendo a la mitad, eso estaría afectando al bucle for interno, lo que significaría que atraviesa el Array "la mitad" del tiempo, por lo tanto sería $O(logn)$ complejidad. Al igual que antes, el bucle while externo es $O(logn)$ por lo que la complejidad global es $O(logn*logn)$ .

Cómo debería "analizar" este algoritmo, ya que siento que las dos respuestas son "viables" pero la de abajo es la que tiene más "sentido".

Answer 1

HINT

Su complejidad resumida es (suponiendo que $n=2^p$ ) $$ \sum_{k=1}^p \left(3\cdot 2^k +1\right) $$

¿Puedes sumar las series geométricas y convertir el resultado en $n$ ?

---

ACTUALIZACIÓN

Para responder a tu pregunta en los comentarios, cada iteración del bucle for interno son 3 operaciones: A[i] búsqueda de valores, s += A[i] y i += 1 (incremento del índice del bucle). Estoy asumiendo que += sea atómica, es decir, que cuente como una sola operación, si en realidad está implementando la asignación y la suma por separado, serán 2 operaciones cada una, por lo tanto 5 operaciones en total.

Finalmente una iteración del bucle exterior necesita m /= 2 con el cheque m > 0 que también asumo que es atómico. Si no es así, necesitarías 3 operaciones aquí, y todo el bucle sería $5 \cdot 2^k+3$ en su lugar.