这个天真的代码计算组合的big-O复杂度是多少?

以下递归算法是一种计算n选择k的(相当低效的)方法:

 int combinationsOf(int n, int k) {
     if (k == 0) return 1;
     if (n == 0) return 0;
     return combinationsOf(n - 1, k) + combinationsOf(n - 1, k - 1);
}

它基于以下递归见解:

实际评估此函数需要很多函数调用。例如,以这种方式计算2选择2将进行以下调用:

 combinationsOf(2, 2)
   |  |
   |  +- combinationsOf(1, 2)
   |       |  |
   |       |  +- combinationsOf(0, 2)
   |       |
   |       +-- combinationsOf(1, 1)
   |             |  |
   |             |  +- combinationsOf(0, 1)
   |             |
   |             +- combinationsOf(1, 0)
   +- combinationsOf(2, 1)
        |  |
        |  +- combinationsOf(2, 0)
        |
        +- combinationsOf(1, 1)
             |  |
             |  +- combinationsOf(0, 1)
             |
             +- combinationsOf(1, 0)

有很多方法可以改善此函数的运行时间-我们可以使用动态编程,使用闭式公式nCk = n! /(k!(n-k)!),等等。但是,我很好奇这种特定算法的效率如何。

该函数作为n和k的函数的big-O时间复杂度是多少?