Character arrays - Time & Space Complexity

Time Complexity: Character arrays

O(n)

Understanding Time Complexity

When working with character arrays, it is important to understand how the time to process them grows as their size increases.

We want to know how the number of steps changes when we read or manipulate these arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

void printChars(char arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%c", arr[i]);
    }
    printf("\n");
}

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

This code prints each character in a character array one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that prints each character.
• How many times: It runs once for each character in the array, so n times.

How Execution Grows With Input

As the array gets longer, the number of print steps grows directly with the number of characters.

Input Size (n)	Approx. Operations
10	10 print steps
100	100 print steps
1000	1000 print steps

Pattern observation: The work grows in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to print all characters grows directly with how many characters there are.

Common Mistake

[X] Wrong: "The loop runs a fixed number of times regardless of array size."

[OK] Correct: The loop depends on the array length, so more characters mean more steps.

Interview Connect

Understanding how loops over character arrays scale helps you explain performance clearly in interviews.

Self-Check

"What if we added a nested loop inside the print loop that also runs n times? How would the time complexity change?"

Practice

1. What is a character array in C used for?

easy

A. To store a sequence of characters, like a word or sentence

B. To store only numbers

C. To perform mathematical calculations

D. To create a list of integers

Solution

1. Step 1: Understand character arrays

   A character array in C is a collection of characters stored in contiguous memory locations.

2. Step 2: Identify its use

   It is mainly used to store text like words or sentences, not numbers or calculations.

3. Final Answer:

   To store a sequence of characters, like a word or sentence -> Option A

4. Quick Check:

   Character array = text storage [OK]

Hint: Character arrays hold text, not numbers or math [OK]

Common Mistakes:

• Thinking character arrays store numbers only
• Confusing character arrays with integer arrays
• Assuming character arrays perform calculations

2. Which of the following is the correct way to declare a character array to hold the word "hello" in C?

easy

A. char word[6] = "hello";

B. char word[5] = {'h', 'e', 'l', 'l', 'o'};

C. char word[] = {'h', 'e', 'l', 'l', 'o', '\0'};

D. char word[5] = "hello";

Solution

1. Step 1: Understand string termination in C

   Strings in C end with a special character '\0' to mark the end.

2. Step 2: Check array size and initialization

   char word[6] = "hello"; declares an array of size 6 (5 letters + '\0') and initializes it with "hello" correctly.

3. Final Answer:

   char word[6] = "hello"; -> Option A

4. Quick Check:

   String needs space for '\0' [OK]

Hint: Remember to include space for '\0' in string arrays [OK]

Common Mistakes:

• Not allocating space for the null terminator '\0'
• Using single quotes for strings
• Declaring array size too small

3. What will be the output of the following C code?

char str[] = "cat";
printf("%c", str[3]);

medium

A. t

B. 0 (null character, no visible output)

C. c

D. Compilation error

Solution

1. Step 1: Understand string indexing

   String "cat" has characters at indices 0:'c', 1:'a', 2:'t', and index 3 is the null terminator '\0'.

2. Step 2: Print character at index 3

   Printing str[3] prints the null character which is invisible, so no visible output appears.

3. Final Answer:

   0 (null character, no visible output) -> Option B

4. Quick Check:

   str[3] = '\0' (null) [OK]

Hint: Remember strings end with '\0' at last index [OK]

Common Mistakes:

• Expecting 't' at index 3 instead of '\0'
• Thinking it causes an error
• Confusing index positions

4. Identify the error in this code snippet:

char name[5];
strcpy(name, "hello world");

medium

A. No error, code works fine

B. Incorrect use of strcpy function

C. Missing #include <string.h>

D. Array size is too small for the string

Solution

1. Step 1: Check array size vs string length

   "hello world" has 11 characters plus '\0' = 12 total, but array size is only 5.

2. Step 2: Understand consequences

   Copying this string will overflow the array, causing undefined behavior.

3. Final Answer:

   Array size is too small for the string -> Option D

4. Quick Check:

   Array must fit string + '\0' [OK]

Hint: Array size must be >= string length + 1 [OK]

Common Mistakes:

• Ignoring array size limits
• Assuming strcpy checks size
• Forgetting null terminator space

5. Given the code below, what will be the output?

char arr[10] = "abc";
arr[3] = 'd';
arr[4] = '\0';
printf("%s", arr);

hard

A. abc\0d

B. abc

C. abcd

D. Runtime error

Solution

1. Step 1: Analyze initial array content

   arr is initialized with "abc" which is 'a','b','c','\0' plus extra space.

2. Step 2: Modify characters and null terminator

   arr[3] = 'd' adds 'd' after 'c', then arr[4] = '\0' sets new string end after 'd'.

3. Step 3: Print the string

   printf prints characters until '\0', so output is "abcd".

4. Final Answer:

   abcd -> Option C

5. Quick Check:

   String ends at arr[4] '\0' [OK]

Hint: Null terminator controls string end in arrays [OK]

Common Mistakes:

• Ignoring manual null terminator placement
• Expecting original string without changes
• Confusing character and string printing