Qunado ele faz refeência a memória, ele está querendo dizer o tamanho da pilha de execução. Ou seja, cada vez que chammos a recursão uma nova função é achamada e o consumo de memória aumenta. Pra resolver esse problema, vamos sempre iniciar a recursão na menor parte:
QUICKSORTE2 (A, p, r)
meio = (p+r)/2
enqunato p < r
q <- particiona(A, p, r)
se q >= meio
QUICKSORTE2 (A, p, q-1)
p <- q + 1
senao
QUICKSORTE2 (A, q+1, r)
r <- q - 1
Note que o pior caso para a memória com esse algorítmo não será quando q estiver na posição r-1. O pior caso vai se dar quando q se encontrar no meio. Nesse caso (M é a qunatida de memória):
$$M(1) = 1$$ $$M(n) = M(n/2)$$
Aviso, o particiona é $O(n)$, no entanto ele consome $O(1)$ em memória. Desenvolvendo pelo método da substitituição:
$$M(n) = a + M(n/2) = a + a + M(n/2) = ia + M(\frac{n}{2^i})$$
$$M(n) = ia + M(\frac{n}{2^i})$$
Suponha que n seja multiplo de 2, ou seja, $n = 2^i$. Dessa forma:
$$M(n) = ia + M(1) = ia + 1 = lg \space n + 1$$
Vaja que no pior caso o nosso consumo de memória $O(lg \space n)$.
Vamos provar por indução que estamos certo. Lembre que a nossa hiótese é: $M(n) =lg \space n + 1$. Para a base, a demonstração é trivial.
$$M(n) = M(n/2)$$
Pela hipótese de indução:
$$M(n) = lg \space \frac{n}{2} + 1 + 1 = lg \space n + 1 $$
Seja $S$ a variável aleatória do valor soma de 1 execução. Seja $X$ a variável aleatória que representa cada número do nosso vetor. $$Y = \begin{cases} 1, & \text{se o número for somado} \\ 0, & \text{c.c.} \end{cases}$$
$$E[S] = \sum_{i=1}{10} i \cdot P(X = i \space \text{e} \space Y = 1) = \sum_{i=1}{10} i \cdot P(X = i)P(Y = 1 | X = i)$$
Note que $P(X=1) = 1/10$ para qualquer $i$.
$$E[S] = \frac{1}{10} \sum_{i=1}^{10} i \cdot P(Y = 1 | X = i) = \frac{1}{10} ( 1 \cdot 0 + 2 \cdot 1 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 0 + 6 \cdot 1 + 7 \cdot 0 + 8 \cdot 1 + 9 \cdot 0 + 10 \cdot 1) = 3$$
Ou seja o valor esperado em uma rodada será $3$, em $n$ rodadas será $3n$, como foi verificado no programa em ruby abaixo:
def SomaPares (v)
soma = 0
v.each do |e|
soma += e if e%2 == 0
end
return soma
end
n = 10000
v = Array.new(n) { rand(1...11) }
puts SomaPares (v)