Count and Say Problem in DSA C - Time & Space Complexity

Time Complexity: Count and Say Problem

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to generate the "count and say" sequence grows as we ask for more terms.

How does the work increase when we want the nth term?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

char* countAndSay(int n) {
    if (n == 1) return strdup("1");
    char* prev = countAndSay(n - 1);
    int len = strlen(prev);
    char* result = malloc(len * 2 + 1);
    int idx = 0, count = 1;
    for (int i = 1; i <= len; i++) {
        if (i < len && prev[i] == prev[i - 1]) {
            count++;
        } else {
            idx += sprintf(result + idx, "%d%c", count, prev[i - 1]);
            count = 1;
        }
    }
    free(prev);
    return result;
}
    

This code generates the nth term of the count and say sequence by building from the previous term.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursion calling countAndSay(n-1) and a loop that scans the previous string to build the current one.
• How many times: The recursion happens n times, and each loop runs over the length of the previous string.

How Execution Grows With Input

Each term is built by reading the previous term, which roughly doubles in length each time.

Input Size (n)	Approx. Operations
1	1 (base case)
5	About 16 operations (length grows roughly doubling each step)
10	About 512 operations (string length grows exponentially)

Pattern observation: The work grows exponentially because each term length roughly doubles, so the total work sums up exponentially.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed roughly doubles with each increase in n, growing very fast.

Common Mistake

[X] Wrong: "The time grows linearly with n because we just call the function n times."

[OK] Correct: Each call processes a string that grows exponentially in length, so the work per call increases a lot, not just the number of calls.

Interview Connect

Understanding how recursion and string growth affect time helps you explain and optimize similar problems in interviews confidently.

Self-Check

"What if we stored all previous terms to avoid repeated recursion? How would the time complexity change?"