Erro no uso de notação assintótica

Estou tentando entender o que há de errado com a seguinte prova da recorrência a seguir

A documentação diz que está errado por causa da hipótese indutiva de que

Digamos que o objetivo final seja provar . Você começa com a hipótese de indução:$T(n) = \mathcal{O}(n)$

para todos os i < n .$T(i) \leq ci$$i < n$

E para completar a prova, você deve mostrar que também.$T(n) \leq cn$

No entanto, você pode deduzir é , o que não é útil para concluir a prova; você precisa de uma constante c para (quase) todo n . Portanto, não podemos concluir nada e T ( n ) = O ( n ) não está provado.$T(n) \leq (c+1)n$$c$$n$$T(n) = \mathcal{O}(n)$

Observe que você está confuso entre o resultado e o processo de prova. E mais um ponto, é realmente Θ ( n log n ) nesse caso, portanto, você pode considerar uma hipótese de indução apropriada para poder provar isso.$T(n)$$\Theta(n \log n)$

Você omitiu alguns passos. Parece que você está tentando provar por indução que , e sua prova é:$T(n) = O(n)$

Suponha que para k < n . Isso significa T ( k ) ≤ $T(k) = O(k)$$k<n$ para alguns c . Em seguida, T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$c$ , então T ( n ) = O ( n ) .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$$T(n) = O(n)$

Esta prova dá errado desde o início: “ para k < n ” não faz sentido. Oh grande é uma noção assintótica: T ( k ) = O ( k ) significa que existe alguma constante c e um limiar N tal que ∀ k ≥ N , T ( k ) ≤ $T(k) = O(k)$$k \lt n$$T(k) = O(k)$$c$ . E, novamente, no final, você não pode concluir que “ T ( n ) = O ( n ) ”, porque isso diz algo sobre a função T como um todo e você só provou algo sobre o valor específico T ( n ) .$\forall k \ge N, T(k) \le c \, k$$T(n)=O(n)$$T$$T(n)$

Você precisa ser explícito sobre o que significa. Talvez sua prova seja:$O$

Suponha que para todos os k < n . Em seguida, T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$k < n$ .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$

Isso não prova um passo indutivo: você começou com , e você provou que para k = n , T ( k ) ≤ ( c + 1 $T(k) \le c \, k$$k=n$ . Este é um limite mais fraco. Veja o que isso significa: T ( k ) ≤ $T(k) \le (c+1) \, k$ meios que C é um limite para a taxa de crescimento de t . Mas você tem uma taxa c que cresce quando k cresce. Isso não é um crescimento linear!$T(k) \le c \, k$$c$$T$$c$$k$

Se você olhar atentamente, perceberá que a taxa aumenta 1 sempre que k dobrar. Então, informalmente, se m = 2 p k então c m = c k + p ; em outras palavras, c k = c 0 log 2 k .$c$$1$$k$$m=2^p k$$c_m = c_k + p$$c_k = c_0 \log_{2} k$

Isso pode ser feito com precisão. Prove por indução que para , T ( k ) ≤ c log 2 ( k ) .$k \ge 1$$T(k) \le c \log_2(k)$

A relação de recorrência é típica para algoritmos de dividir e conquistar que dividem os dados em duas partes iguais em tempo linear. Esses algoritmos operam em tempo (não S ( n ) ).$\Theta(n\,\mathrm{log}(n))$$O(n)$

Para ver qual é o resultado esperado, você pode verificar a relação de recorrência contra o teorema mestre . A divisão é e o trabalho extra realizado é n ; log 2 ( 2 ) = 1, então este é o segundo caso para o qual o crescimento é Θ ( $2T(n/2)$$n$$\log_2(2) = 1$ .$\Theta(n\,\log(n))$

I'm extending the answer already given, perhaps only by explaining my comment in more detail.

Como a adivinhação pode ser claramente difícil e tediosa, às vezes existem métodos melhores. Um desses métodos é o Teorema dos Mestres . O nosso recorrência é agora a forma de , onde um ≥ 1 e b > 1 são constantes e f ( n ) uma função. Note-se que no nosso caso ⌊ n / 2 ⌋ pode ser interpretada no sentido de n /$T(n) = a T(n/b) + f(n)$$a \geq 1$$b > 1$$f(n)$$\lfloor n/2 \rfloor$$n/2$. Para ser tecnicamente exato, nossa recorrência pode não estar bem definida, pois pode não ser um número inteiro. No entanto, isso é permitido, uma vez que não afetará o comportamento assintótico da recorrência. Portanto, geralmente achamos conveniente soltar pisos e tetos. A prova formal disso é um pouco entediante, mas o leitor interessado pode encontrá-lo, por exemplo, no Cormen et al. livro .$n/2$

In our case, we have $a = 2$, $b = 2$, $f(n) = \Theta(n)$. This means that we have $n^{\log_b a} = n^{\log_2 2} = n$. The second case of the Master theorem applies since $f(n) = \Theta (n)$, and we have the solution $T(n) = \Theta (n \log n)$.