Как подходить к поиску сложности выполнения рекурсивного алгоритма?

Question

Я написал код ниже, чтобы перечислить все комбинации данного массива.

Но я изо всех сил пытаюсь вычислить Big-O сложность этой рекурсивной функции.

public static void getCombinations(int[] input, int start,
                                   List<Integer> current,
                                   List<List<Integer>> output)
{
  output.add(new ArrayList<Integer>(current));

  if( start >= input.length )
    return;

  for(int ind=start; ind<input.length; ind++) {
    current.add(input[ind]);
    getCombinations(input, ind+1, current, output);
    current.remove(current.size()-1);
  }
}

Методвызывается как:

getCombinations(input, 0 /*start*/, current, output);

Пример ввода:

[1,2,3]

Вывод:

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

Answer 1

Думая дальше, я думаю, что это можно записать в виде:

(1) T(N)  = T(N-1) + T(N-2) + T(N-3) + .... + 1
(2) T(N-1)=          T(N-2) + T(N-3) + .... + 1

Итак, подставив (2) в (1) выше,

T(N) = T(N-1) + T(N-1)
     = 2*T(N-1)
     = 2*(2*T(N-2)) = 2*2*T(N-2) = 2*2*2*T(N-3) etc
     = O(2^N)