Enunciado:
- Seja T a função definida sobre os números naturais pela seguinte recorrência: T(0) = 0 e T(n ) = T(⌈(n−1)/2⌉) + 1 para n = 1,2,3,4,… Prove (por indução em n) que T(n ) ≤ log n + 1 para n = 1,2,3,4,…
Qual a base desse log? Deveria ser lg?
Muito obrigado!
Sim, este log é na base 2.