# What is the time complexity of the following loop? [duplicate]

function (n)
i = 1
s = 1
while (s <= n)
i = i+1
s = s*i
print "*"
end


## marked as duplicate by fade2black, David Richerby, Evil, quicksort, JuhoDec 23 '17 at 16:12

Assuming all operations are done in constant time, this loop runs in $\Theta(n!^{-1})$ where $!^{-1}$ is the inverse factorial. Intuitively, the program will enter the loop $i$ times, $i$ being the smallest integer so that $i!\geq n$.
• Factorial grows faster than exponential. Hence, the natural logarithm (the inverse of the exponential) grows faster than the inverse of the factorial. It follows (if you change the logarithm's base) that the inverse factorial is indeed $O(\log n)$. – Roukah Dec 20 '17 at 20:26