Complexidade temporal deste loop for: para (i = 2; i <N; i = i * i)?
Estamos aprendendo sobre a complexidade do tempo agora e estou tendo muitos problemas com este exemplo.
for (i = 2; i < n; i = i * i)
{
... do something ...
}
O professor disse que era O (sqrt (N)), mas não tenho certeza se estou convencido. Afinal, se N = 16, ele roda apenas duas vezes, não quatro, certo?
Minha abordagem à solução: 2 ^ (2k) = N, onde k é o número de vezes que o loop é executado. Removendo os fatores constantes, k executa os tempos de log (N). Onde estou errado aqui? Obrigado por qualquer conselho sobre o assunto.