Поскольку i имеет конкретный тип (int), он ограничен, и сложность его выполнения O(1).
Кроме того, функция настолько быстро растет, что емкость int превышено по состоянию на шестой член.
Если считать, что данный код является псевдокодом и что int s не ограничен, то можно использовать
i[k]² <= i[k+1] = i[k]² + i[k] <= a i[k]²
где a - это константа, которую необходимо определить.
Затем берется логарифм по основанию-2
2 lg i[k] <= lg(i[k+1]) <= 2 lg(i[k]) + lg(a)
и по индукции
2^m lg(i[k]) <= lg(i[k+m]) <= 2^m lg(i[k]) + (2^m - 1) lg(a) <= 2^m lg(a.i[k])
Снова берется логарифм,
m + lg(lg(i[k])) <= lg(lg(i[k+m])) <= m + lg(lg(a.i[k]))
также написано
lg(lg(i[k+m])) - lg(lg(a.i[k])) <= m <= lg(lg(i[k+m])) - lg(lg(i[k]))
Поскольку m представляет количество итераций, следующих за k первым, для n = i[k + m] у нас есть
lg(lg(n)) - lg(lg(a.i[k])) <= m <= lg(lg(n)) - lg(lg(i[k]))
В частности, с k=0 мы можем взять a = 3/2 и
lg(lg(n)) - lg(lg(3)) <= m <= lg(lg(n)) - lg(lg(2))
Это доказывает m = Θ(lg(lg(n)).