Dada função F definida como: F(1) = 1 F(N) = F(N/2) + 1, para N ≥ 2. Suponha N=2k, para k=1, 2, 3, ... Selecione a opção correta com a...

Podemos encontrar a fórmula fechada para a função F(2k) usando a técnica de substituição. F(2k) = F(2k/2) + 1 F(2k) = F(k) + 1 Substituindo novamente, temos: F(k) = F(k/2) + 1 F(k) = F(k/2^2) + 2 F(k) = F(k/2^3) + 3 ... F(k) = F(k/2^i) + i Quando k/2^i = 1, temos i = log2(k). Substituindo na equação acima, temos: F(k) = F(1) + log2(k) F(k) = 1 + log2(k) Portanto, a opção correta é a letra a) F(N) = 1 + log2 N.