function (n)
    i = 1
    s = 1
    while (s <= n)
        i = i+1
        s = s*i
        print "*"
  • 1
    $\begingroup$ This place isn't a machine that answers questions. You should have formatted your message and gave what you've tried to solve this. $\endgroup$ – user80502 Dec 20 '17 at 17:42
  • $\begingroup$ I'm sorry. I am new to this place. I'll definitely do that next time. $\endgroup$ – Ken Adams Dec 20 '17 at 19:09
  • $\begingroup$ @dylan61 The problem here isn't the formatting. It's that the question is just a problem dump ("Here's an exercise -- please solve it for me!") and that it's already covered by our reference question. $\endgroup$ – David Richerby Dec 21 '17 at 22:13

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$.

  • $\begingroup$ Thanks. I've never come across this function while computing complexity. Is this function O(log(n)) $\endgroup$ – Ken Adams Dec 20 '17 at 19:12
  • $\begingroup$ 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)$. $\endgroup$ – Roukah Dec 20 '17 at 20:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.