Palindrome Detection in DSA C - Time & Space Complexity

Time Complexity: Palindrome Detection

O(n)

Understanding Time Complexity

We want to know how the time needed to check if a word or phrase is a palindrome changes as the input gets longer.

The question is: how does the number of steps grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>
#include <string.h>

int isPalindrome(char str[]) {
    int left = 0;
    int right = strlen(str) - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}
    

This code checks if a string reads the same forwards and backwards by comparing characters from both ends moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters at positions from the start and end of the string.
• How many times: Up to half the length of the string (n/2 times).

How Execution Grows With Input

As the string gets longer, the number of character comparisons grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5 comparisons
100	50 comparisons
1000	500 comparisons

Pattern observation: The number of steps grows linearly with input size, but only half as many comparisons are needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a palindrome grows in direct proportion to the length of the input string.

Common Mistake

[X] Wrong: "The palindrome check takes constant time because it just compares characters."

[OK] Correct: The number of comparisons depends on the string length, so longer strings take more time.

Interview Connect

Understanding how palindrome detection scales helps you explain your code clearly and shows you can analyze efficiency, a key skill in interviews.

Self-Check

"What if we checked only every other character instead of all? How would the time complexity change?"