time-complexity - 我需要帮助找出这个函数的时间复杂度

Question

如果有人可以逐步完成该功能并解释他们将如何找到时间复杂度，我将非常感激。说到这个，我还是有点迷茫。

int exp2 (int a, int b)
{
        if (b==1)
        return a;
    Else
        return a*exp2(a,b-1);
}

标签： time-complexitybig-o

Answer 1

O(b)。

请注意，该函数将重复b次，执行单个操作（乘法）。

(1) exp(4, 20) = 4 * exp(4, 19)
(2) exp(4, 19) = 4 * exp(4, 18) 
(3) exp(4, 18) = 4 * exp(4, 17)  
...
(b) exp(4, 1) = 4