Obtenha a equação matemática referente á análise do pior e melhor caso do fragmento de código abaixo:
for (i = 1; i <= N; i=2*i)
2 printf("%d",i);

Passo 1

Estamos com o fragmento de código que faz um laço de repetição onde a variável i começa em 1 e, a cada iteração, é dobrada até ultrapassar N. O conteúdo é análise de complexidade temporal de algoritmos, e vamos precisar contar quantas vezes esse laço é executado.

Passo 2

Em cada iteração, o valor de i dobra. Se chamarmos de k o número de iterações completas até i ultrapassar N, teremos ao final da iteração k que i = 2^k.
O laço continua enquanto i <= N. Então buscamos o maior k tal que
2^k <= N

Passo 3

Para encontrar k, aplicamos o logaritmo de base 2 em ambos os lados:
k <= log2 N

Passo 4

Como k é inteiro, temos k = lfloorlog2 Nrfloor.
O número total de iterações é esse k mais a iteração inicial (quando i=1, correspondente a 2^0), ou seja:
T(N) = lfloorlog2 Nrfloor + 1

Passo 5

Esse valor de T(N) independe de casos de entrada diferentes, logo o melhor e o pior caso são iguais.

Resposta

Melhor caso: T(N)=lfloorlog2 Nrfloor + 1. Pior caso: T(N)=lfloorlog2 Nrfloor + 1.

Exercícios relacionados