Palindrome Partitioning Using Backtracking in DSA C - Time & Space Complexity

Time Complexity: Palindrome Partitioning Using Backtracking

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed to find all palindrome partitions grows as the input string gets longer.

Specifically, how does the backtracking process scale with the string size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool isPalindrome(char* s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) return false;
        start++;
        end--;
    }
    return true;
}

void backtrack(char* s, int start, int len) {
    if (start == len) {
        // store current partition
        return;
    }
    for (int end = start; end < len; end++) {
        if (isPalindrome(s, start, end)) {
            backtrack(s, end + 1, len);
        }
    }
}

This code finds all ways to split the string into palindrome parts using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries every possible substring start to end.
• How many times: For each start position, it checks all ends, and calls backtrack recursively for the rest.
• Palindrome check: Each substring check scans characters between start and end.
• Dominant operation: The recursive calls combined with palindrome checks cause exponential growth.

How Execution Grows With Input

As the string length grows, the number of palindrome partitions grows very fast.

Input Size (n)	Approx. Operations
10	Thousands of checks and recursive calls
100	Millions to billions of operations
1000	Operations grow beyond practical limits

Pattern observation: The work grows exponentially because each position can split in many ways, and palindrome checks add extra cost.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time grows very fast, roughly doubling with each added character, multiplied by the cost to check palindromes.

Common Mistake

[X] Wrong: "The algorithm runs in polynomial time because it just loops over the string."

[OK] Correct: The recursive splitting creates many branches, causing exponential growth, not just simple loops.

Interview Connect

Understanding this complexity helps you explain why backtracking can be slow and when to expect exponential time, a key skill in problem solving.

Self-Check

"What if we used memoization to store palindrome checks? How would the time complexity change?"