Какова временная сложность этой рекурсивной функции?

Question

public static int[] index(int input[],int x,int i){   
    if (i==0) {
        if (input[i]==x)
            return new int[] {0};
        else
            return new int[] {};
    }
    int[] c = index(input, x, i-1);
    if (input[i] == x) {
        int len = c.length + 1;
        int[] a = new int[len];
        int j;
        for (j = 0; j <= c.length - 1; j++)
            a[j] = c[j];
        a[j] = i; // j++ 
        return a;
    }
    return c;
}

Какова временная сложность этой рекурсивной функции, которая возвращает все индексы вхождения элемента x во входной массив?