两个简单的递归函数大O符号(Big-O notation for two simple recurs

我有两个递归函数在Python和单纯只是想知道他们的大O符号。什么是大O为这些？

def cost(n):
    if n == 0:
        return 1
    else:
        return cost(n-1) + cost(n-1)

def cost(n):
    if n == 0:
        return 1
    else:
        return 2*cost(n-1)

Answer 1:

让我们用递推关系来解决这个问题！第一个功能的运行时可以递归描述为

T（0）= 1
T（N + 1）= 2T（N）+ 1

也就是说，基本情况下需要一个时间单元来完成，否则我们对这个问题的小实例两个递归调用和做安装和清理一定量的工作。在这种复发扩大了一些条款，我们得到

T（0）= 1
T（1）= 2T（0）+ 1 = 2 + 1 = 3
T（2）= 2T（1）+ 1 = 2×3 + 1 = 7
T（3）= 2T（2）+ 1 = 2×7 + 1 = 15

这一系列1，3，7，15，...可能看起来很熟悉，因为这是2月^{1日至一日} ^，2月2日至1日，2月^3日至 1日，等更一般地，我们可以证明

T（N）= 2 ^{N + 1} - 1

我们可以通过归纳做到这一点。作为我们的碱的情况下，T（0）= 1 = 2 ¹ - 1，因此，如权利要求保持对于n = 0。现在假设，对于一些n表示T（N）= 2 ^{N + 1} - 1。然后，我们有

T（N + 1）= 2T （N）+ 1 = 2（2 N + 1 - 1）+ 1 = 2 N + 2 - 2 + 1 = 2 N + 2 - 1

我们就大功告成了！由于这种复发工程以2 ^{N + 1} - 1 = 2（2 ^N） - 1，我们有运行时间是Θ（2 ^N）。

第二功能的运行时可以递归被描述为

T（0）= 1
T（N + 1）= T（N）+ 1

扩大了一些术语：

T（0）= 1
T（1）= T（0）+ 1 = 1 + 1 = 2
T（2）= T（1）+ 1 = 2 + 1 = 3
T（3）= T（2）+ 1 = 3 + 1 = 4

这给了1，2，3，4，...，所以更普遍，我们可以猜测

T（N）= N + 1

我们可以再次感应证明这一点。作为碱的情况下，如果n = 0，则T（0）= 1 = 0 + 1。对于感应步骤中，假定对于某些n表示T（N）= N + 1。然后

T（N + 1）= T（N）+ 1 = N + 1 + 1 = N + 2

我们就大功告成了！由于运行时为n + 1，则运行时是Θ（n）中。

希望这可以帮助！

Answer 2:

使用递归树（通过可视化图）寻找成本。

该函数的成本递推关系（n）的

                    T(n) = 2T(n-1)+c

If at kth level input size become 0 (base condition where func terminates)
                                           n-k =0
                                              k=n


Total cost of the function (adding cost of each level) :
             T(n) = 2^0*c+ 2^1*c + 2^2*c + 2^3*c +.. .. . .+ 2^n * c
                  = O(2^n)

类似的方法，我们可以找到第二个函数的时间复杂度。