Are you taking CLEP classes? Try clep.ai
| preferred AP College board partner for AP classes
AP Computer Science A/Unit 10: Recursion
Start Practice TestPractice Test
About Exam
hard

Recursive Permutation Time Complexity

Mark
< Prev
Next >

The permute method below is designed to generate all permutations of an integer array. What is the time complexity of this method?

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 that the swap method correctly swaps two elements in the array.

A

O(n!)

B

O(2^n)

C

O(n log n)

D

O(n^2)

Hint
Did You Know?
Explain Why
Explain All Answers
Check Answer
Show Correct Answer
Report Question

Question Leaderboard

Not enough data yet to show leaderboard.

AI Tutor

How can I help?

APFIVE © 2020.
Email: apfive@apfive.org|Privacy Policy|