time-complexity - 计算函数 f2 的时间和空间复杂度

Question

我有这个功能，我正在尝试计算时间和空间复杂度，我得到了答案，但我不确定它是否正确，我想知道这是否正确

   void f1(int n)
    {
        int i,j,k=0;
        for(int i=n/2; i<=n; i++)
        {
            for(int j=2; j<=i; j*=2)
            {
                k+=n;
            }
        }
        
        free(malloc(k));
    }

我的结果：

对于外部 for 循环，它非常简单 O(n)。

对于内部循环，我们每次迭代都有 log((n/2)+i)，所以基本上每次迭代都有 log(n)。

所以总时间复杂度是 O(n*log(n))

对于空间复杂度，只要 k 接收到它的最终值，它就是 O(k)，因为 k 的最终值是 k+nn log(n) 次，所以在所有迭代之后，我们有 k=n^2 log(n)，所以空间复杂度为 O((n^2)*log(n))。

这个对吗？

标签： time-complexityspace-complexity