Time complexity of an interview question

Anonymous User

205

I had an interview question where given a n dimensional list I had to find out the sum
getDim -> returns the dimensions .e.g [3,2,6,1].
getElement([i,j,k,l]) -> return list[i][j][k][l] .

Obviously dimensions can be any set , eg: 3 dimensions [2,3,1]

How would i go about making sense of the time complexity for the following recursion method: I know generic formula for recursion is b ^ d where b are the branches and d is the max recursion depth. based on the code below I assume b would be average of the dimensions and d is the max dimension?

public List<int[]> getAllIndex (int[] dimensions) {
            List<int[]> result = new ArrayList<int[]>();
            int[] index = new int[dimensions.length];
            helper(result, index, 0, dimensions);
            return result;. 
    }
   
    private void helper(List<int[]> result, int[] index, int depth, int[] dimensions) {
            if (depth == dimensions.length) {
                    result.add(index.clone());
                    return;
            }
            int currentDimension = dimensions[depth];
            for (int i=0; i<currentDimension; i++) {
                    index[depth] = i;
                    helper(result, index, depth+1, dimensions);
            }
    }

Comments (1)