python - 有理由地运行以下功能的复杂性

Question

我无法找到以下函数的运行复杂性，因为这里连接了 3 个东西 1:输入大小 2:i 值 3:s 值。请帮助我找到推理的运行复杂性。

def function(n):
    i=s=1
    while s<n:
        i=i+1
        s=s+i
        print("*")
function(20)

Answer 1

这是O(sqrt(n)) 算法。

The loop runs i times such that `1+2+..i<=n.`[maximum i] 
or
i*(i+1)/2<=n or i^2/2<=n or i<=sqrt(2n) 
~O(sqrt(n))