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?"

Practice

1. What does the expression str[0] represent when str is a string in C?

easy

A. The first character of the string

B. The length of the string

C. The last character of the string

D. A pointer to the string

Solution

1. Step 1: Understand string indexing in C

   In C, strings are arrays of characters. Indexing starts at 0, so str[0] accesses the first character.

2. Step 2: Identify what str[0] returns

   It returns the character stored at the first position of the string, not the length or pointer.

3. Final Answer:

   The first character of the string -> Option A

4. Quick Check:

   str[0] = first character [OK]

Hint: Remember: string indexing starts at zero in C [OK]

Common Mistakes:

• Confusing character access with string length
• Thinking indexing starts at 1
• Mixing pointer and character access

2. Which of the following is the correct way to traverse a string str of length n in C using a for loop?

easy

A. for (int i = 1; i < n; i++)

B. for (int i = 0; i <= n; i++)

C. for (int i = 0; i < n; i++)

D. for (int i = 1; i <= n; i++)

Solution

1. Step 1: Understand string indexing and loop bounds

   String indices in C start at 0 and go up to n-1 for length n.

2. Step 2: Choose loop condition to cover all characters

   The loop should run from 0 to n-1, so i < n is correct.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option C

4. Quick Check:

   Loop from 0 to n-1 = for (i=0; i<n; i++) [OK]

Hint: Loop from 0 to less than length for strings [OK]

Common Mistakes:

• Using <= n causes out-of-bounds access
• Starting loop at 1 misses first character
• Confusing string length with last index

3. What is the output of the following C code?

char str[] = "hello";
for (int i = 0; i < 5; i++) {
    printf("%c-", str[i]);
}

medium

A. hello-

B. h-e-l-l-o-

C. h e l l o

D. h-e-l-l-o

Solution

1. Step 1: Analyze the loop and print statement

   The loop runs from i=0 to 4, printing each character followed by a dash.

2. Step 2: Trace each iteration output

   Characters printed: 'h-', 'e-', 'l-', 'l-', 'o-'. Combined output is "h-e-l-l-o-".

3. Final Answer:

   h-e-l-l-o- -> Option B

4. Quick Check:

   Each char + '-' printed = h-e-l-l-o- [OK]

Hint: Look at printf format and loop range carefully [OK]

Common Mistakes:

• Ignoring the dash after each character
• Printing the whole string once instead of chars
• Confusing spaces with dashes

4. Identify the error in the following code snippet that tries to print each character of a string str.

char str[] = "world";
for (int i = 1; i <= 5; i++) {
    printf("%c", str[i]);
}

medium

A. Both A and B are errors

B. Loop condition should be i < 5 instead of <= 5

C. No error, code works fine

D. Loop starts at 1 and misses the first character

Solution

1. Step 1: Check loop start index

   Loop starts at 1, so it skips str[0] which is the first character.

2. Step 2: Check loop end condition

   Loop runs while i <= 5, but valid indices are 0 to 4. Accessing str[5] causes out-of-bounds error.

3. Final Answer:

   Both A and B are errors -> Option A

4. Quick Check:

   Start at 0 and use i < length to avoid errors [OK]

Hint: Loop from 0 to less than length to avoid errors [OK]

Common Mistakes:

• Starting loop at 1 and missing first char
• Using <= length causing out-of-bounds access
• Ignoring array indexing rules

5. Given a string str of unknown length, which of the following code snippets correctly prints all characters until the null terminator in C?

hard

A. for (int i = 0; str[i] != '\0'; i++) { printf("%c", str[i]); }

B. for (int i = 0; i < strlen(str); i++) { printf("%c", str[i]); }

C. while (*str != '\0') { printf("%c", *str); str++; }

D. All of the above

Solution

1. Step 1: Analyze for (int i = 0; str[i] != '\0'; i++) { printf("%c", str[i]); }

   Loops until character is not null terminator, printing each character. Correct method.

2. Step 2: Analyze for (int i = 0; i < strlen(str); i++) { printf("%c", str[i]); } and C

   for (int i = 0; i < strlen(str); i++) { printf("%c", str[i]); } uses strlen to get length, then loops printing characters. while (*str != '\0') { printf("%c", *str); str++; } uses pointer traversal until null terminator. Both are correct.

3. Step 3: Combine results

   All three methods correctly print the string characters until the null terminator.

4. Final Answer:

   All of the above -> Option D

5. Quick Check:

   All methods stop at '\0' and print chars [OK]

Hint: Any loop stopping at '\0' prints full string safely [OK]

Common Mistakes:

• Not checking for null terminator causing overflow
• Using wrong loop conditions
• Modifying string pointer incorrectly