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.