Next Permutation of Array in DSA Python - Time & Space Complexity

Time Complexity: Next Permutation of Array

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next permutation changes as the array size grows.

Specifically, how many steps does the algorithm take when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

This code finds the next lexicographical permutation of the input list of numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops scanning parts of the array and one slice reversal.
• How many times: Each loop runs at most once from the end towards the start, scanning up to n elements.

How Execution Grows With Input

As the array size grows, the loops and reversal may scan more elements, but each step still goes through the array at most once.

Input Size (n)	Approx. Operations
10	Up to about 30 steps
100	Up to about 300 steps
1000	Up to about 3000 steps

Pattern observation: The number of steps grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the next permutation grows linearly with the size of the array.

Common Mistake

[X] Wrong: "The algorithm checks all possible permutations, so it must be factorial time."

[OK] Correct: The algorithm smartly finds the next permutation by scanning the array only a few times, not generating all permutations.

Interview Connect

Understanding this linear time approach shows you can handle array manipulation efficiently, a skill often needed in real coding problems.

Self-Check

"What if the input array is already the highest permutation? How does that affect the time complexity?"