小编Sin*_*war的帖子

我认为下面代码的时间复杂度应该是 O(1)，因为最坏的情况可能是 log 1000 base 2 或某些确定的值。但我不确定，因为它的时间确实随着输入的变化而变化，并且给定的答案是 O(n)，我对他们是如何得到这个感到非常困惑。如果我们增加 n，函数被调用的次数就会减少，那么它是 O(1/n) 吗？有可能吗？

#define LIMIT 1000

    void fun2(int n)
    {
      if (n <= 0)
         return;
      if (n > LIMIT)
        return;
      cout<<n<<" ";
      fun2(2*n);
      cout<<n<<" ";
    }