Recursive Permutation Time Complexity
What is the time complexity of the permute method, which generates all permutations of an array?
public void permute(int[] arr, int start) {
if(start == arr.length) {
System.out.println(Arrays.toString(arr));
return;
}
for(int i = start; i < arr.length; i++) {
swap(arr, start, i);
permute(arr, start + 1);
swap(arr, start, i);
}
}
// Assume swap() correctly swaps two elements in the array.
A
O(n!)
B
O(n log n)
C
O(2^n)
D
O(n^2)
Question Leaderboard
Not enough data yet to show leaderboard.
APFIVE