algorithm - 以下递归代码片段的时间和空间复杂度是多少？

Question

下面是一个递归函数，用于计算二项式系数“C”的值，即组合!我希望根据 N 和 K(假设我们正在计算 NCK)来理解这段代码的时间和空间复杂度。

public class ValueOfBinomialCofecientC {

static int globalhitsToThisMethod = 0;

    public static void main(String[] args) {
        // Calculate nCk. 
        int n = 61, k = 55;
        long beginTime = System.nanoTime();
        int ans = calculateCombinationVal(n, k);
        long endTime = System.nanoTime() - beginTime;

        System.out.println("Hits Made are : " +globalhitsToThisMethod + " -- Result Is : " + ans + " ANd Time taken is:" + (endTime-beginTime));
    }

    private static int calculateCombinationVal(int n, int k) {
        globalhitsToThisMethod++;
        if(k == 0 || k == n){
            return 1;
        } else if(k == 1){
            return n;
        } else {
            int res = calculateCombinationVal(n-1, k-1) + calculateCombinationVal(n-1, k);
            return res;
        }
    }

}

Answer 1

        Recursive equation : T(n ,k) = C + T(n-1,k-1) + T(n-1,k);
                             where, T(n ,k) = time taken for computing NCK 
                                    C = constant time => for above if-else 
        
        

                  T(n ,k)
                     | --> work done = C =>after 'C' amount of work  function is split --> level-0
         ____________________________________________ 
        |                                            |
    T(n-1,k-1)                                     T(n-1,k)
        | --> C                                      | --> C => Total work = C+C = 2C -->leve1-1
   ____________________________              _______________________
  |                            |            |                       |
T(n-2,k-2)                T(n-2,k-1)      T(n-2,k-1)            T(n-2,k)

      using tree method : total work done at level-2 = 4C => 2*2*C
                                             level-3 = 8C => 2*2*2*C

        max level tree can grow = max(k+1,n-k-1) 
        => T(n ,k) = 2^max(k+1,n-k-1) * C
           let C=1
           => T(n) = 2^max(k+1,n-k+1)

        T(n) = O(2^n) , k < n/2;
             = O(2^k) , k > = n/2;