递归乘法函数rec_mul的最坏时间复杂度（大O表示法）争议辨析

先看目标函数：

def rec_mul(a:int, b:int) -> int:
        if b == 1:
            return a
        
        if a == 1:
            return b
        
        else:
            return a + rec_mul(a, b-1)

你和朋友的争议核心在于对复杂度分析中“n”的定义不一致：

• 你的结论（O(n)）是把n定义为输入参数的数值大小：
  当a和b都大于1时，函数会递归调用b-1次（每次b减1直到触发b==1的终止条件），每次递归仅执行一次加法操作，没有额外分支或嵌套递归，总操作次数和b的数值成正比，时间复杂度为O(b)。如果把n看作输入的数值规模（比如取max(a,b)为n），那就是O(n)，这个结论在常规算法复杂度语境下是正确的。

• 你朋友的结论（O(2^n)）是把n定义为输入参数的二进制位数：
  一个n位的二进制正整数最大取值是2^n -1，如果b取这个最大值，递归调用次数就是2^n -2，此时时间复杂度确实是O(2^n)。但这种定义属于“输入规模按位数计算”的场景，通常仅在讨论密码学、位运算相关算法时才会默认采用，常规数值运算的算法分析不会这么定义。

总结：在无特殊说明的情况下，该函数的最坏情况时间复杂度是O(max(a,b))，若用n代表输入的数值规模，就是O(n)。

内容的提问来源于stack exchange，提问作者Cat_in_the_hat