String Traversal and Character Access in DSA C - Time & Space Complexity

Time Complexity: String Traversal and Character Access

O(n)

Understanding Time Complexity

When we look at how fast a program runs that reads each letter in a word, we want to know how the time changes if the word gets longer.

We ask: How does the time to check all letters grow as the word grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

void printChars(char *str) {
    int i = 0;
    while (str[i] != '\0') {
        printf("%c ", str[i]);
        i++;
    }
}

int main() {
    char word[] = "hello";
    printChars(word);
    return 0;
}
    

This code goes through each letter in a word and prints it one by one until it reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character until the end of the string.

How Execution Grows With Input

As the word gets longer, the program checks more letters one by one.

Input Size (n)	Approx. Operations
10	About 10 checks and prints
100	About 100 checks and prints
1000	About 1000 checks and prints

Pattern observation: The number of steps grows directly with the number of letters.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the length of the string.

Common Mistake

[X] Wrong: "Accessing each character is instant and does not add up."

[OK] Correct: Each character must be checked one by one, so the total time adds up as the string gets longer.

Interview Connect

Understanding how reading each letter takes time helps you explain how programs handle text efficiently, a useful skill in many coding tasks.

Self-Check

"What if we changed the loop to only check every second character? How would the time complexity change?"