Complejidad de tiempo de este ciclo for: for (i = 2; i <N; i = i * i)?

Estamos aprendiendo sobre la complejidad del tiempo en este momento y estoy teniendo muchos problemas con este ejemplo.

for (i = 2; i < n; i = i * i)
{
     ... do something ...
}

El profesor dijo que era O (sqrt (N)), pero no estoy seguro de estar convencido. Después de todo, si N = 16, solo se ejecuta 2 veces, no 4 ¿verdad?

Mi enfoque para la solución: 2 ^ (2k) = N, donde k es el número de veces que se ejecuta el ciclo. Eliminando los factores constantes, k ejecuta log (N) veces. ¿Dónde me estoy equivocando aquí? Gracias por cualquier consejo al respecto.