Как рассчитать сложность этой функции?

Question

Мне интересно, какова временная сложность внутреннего цикла for, это sqrt (n) или log (n)?

void foo(int n)
{
 for (int i=0; i<n*n; ++i)
     for (int j=1; j*j<n; j*=2)
         printf("Hello there!\n");
}

Answer 1

j во внутреннем цикле for будет принимать значения 1,2,4, ... 2 ^ t

Также в соответствии с заданным ограничением, 2 ^ 2t = n

Итак, t =(1/2) logn

Поэтому внутренний цикл должен иметь временную сложность O (log (n))

Answer 2

Я думаю, что внутренний цикл for имеет сложность O (sqrt (n)). Чтобы сделать это O (log (n)), внутренний цикл for должен выглядеть примерно так:

EDIT

Это должно быть O (log (n)).