Complejidad Parte 1 Find Sequences

[bthompsonl]

Me surgió una duda respecto a la complejidad pedida. El enunciado dice que debe ser O(QxN), pero el algoritmo rolling hash que se recomienda tiene complejidad O(N+M), por lo tanto si para cada una de las Q consultas se usa ese algoritmo la complejidad queda en O(Q(N+M)). No se si habrá que modificarlo para llegar a la complejidad pedida, he estado pegado en esto varios días y no encuentro la manera. O quizás como en el problema N es mucho mayor a M la diferencia entre N y N+M es insignificante y por ende las complejidades O(QxN) y O(Q(N+M)) son casi iguales?

[benjavicente]

Se sabe que $M$ es entre 0 y $N$, por lo tanto, $M = N \times C$ con C un valor entre 0 y 1.

$$O(N + M) = O(N + N \times C) = O(N \times (1 + C)) = O(N)$$

No se puede hacer al revés, dado que la $C$ en ese caso podría tener valor infinito.