Действительно ли O(log(log(n)))
просто O(log(n))
, когда дело доходит до временной сложности?
Согласны ли вы с тем, что эта функция g()
имеет временную сложность O(log(log(n)))
?
int f(int n) {
if (n <= 1)
return 0;
return f(n/2) + 1;
}
int g(int n) {
int m = f(f(n));
int i;
int x = 0;
for (i = 0; i < m; i++) {
x += i * i;
}
return m;
}