Character arrays in C++ - 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 the array gets bigger.

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.

char arr[] = "hello world";
int length = 0;

while (arr[length] != '\0') {
    length++;
}
    

This code counts how many characters are in the array until it finds the end marker.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each character in the array one by one.
• How many times: Once for each character until the end marker is found.

How Execution Grows With Input

As the array gets longer, the number of checks grows directly with its size.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows directly with the number of characters.

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 it runs more times as the array gets longer.

Interview Connect

Understanding how loops over character arrays scale helps you explain simple string operations clearly in interviews.

Self-Check

"What if we used a function that copies the array instead of just counting? How would the time complexity change?"

Practice

1. What is the purpose of the null terminator '\0' in a character array in C++?

easy

A. It marks the end of the string stored in the array.

B. It initializes all characters to zero.

C. It increases the size of the array by one.

D. It converts characters to uppercase.

Solution

1. Step 1: Understand the role of '\0' in character arrays

   The null terminator '\0' is a special character used to mark the end of a string in C++ character arrays.

2. Step 2: Identify its effect on string handling

   Functions that work with strings stop reading characters when they encounter '\0', so it tells where the string ends.

3. Final Answer:

   It marks the end of the string stored in the array. -> Option A

4. Quick Check:

   Null terminator = end of string [OK]

Hint: Remember '\0' ends the string, like a period ends a sentence. [OK]

Common Mistakes:

• Thinking '\0' initializes characters to zero
• Confusing '\0' with increasing array size
• Assuming '\0' changes character case

2. Which of the following is the correct way to declare a character array to hold the word "code" including the null terminator?

easy

A. char word[3] = {'c', 'o', 'd', '\0'};

B. char word[4] = {'c', 'o', 'd', 'e'};

C. char word[4] = "code";

D. char word[5] = {'c', 'o', 'd', 'e', '\0'};

Solution

1. Step 1: Count characters and null terminator

   The word "code" has 4 letters plus 1 null terminator '\0', so the array size must be 5.

2. Step 2: Check each option's array size and initialization

   char word[5] = {'c', 'o', 'd', 'e', '\0'}; correctly declares a char array of size 5 and includes the null terminator explicitly.

3. Final Answer:

   char word[5] = {'c', 'o', 'd', 'e', '\0'}; -> Option D

4. Quick Check:

   Array size = letters + 1 for '\0' [OK]

Hint: Array size = number of chars + 1 for '\0'. [OK]

Common Mistakes:

• Forgetting to add space for the null terminator
• Using incorrect array size
• Not including '\0' explicitly when needed

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

char arr[6] = "hello";
arr[0] = 'H';
std::cout << arr << std::endl;

medium

A. hello

B. Hello

C. H

D. Compilation error

Solution

1. Step 1: Understand the initial array content

   The array is initialized with "hello" which includes the null terminator automatically, so arr = {'h','e','l','l','o','\0'}.

2. Step 2: Modify the first character and print

   Changing arr[0] to 'H' updates the first letter. Printing arr outputs the string until '\0', so output is "Hello".

3. Final Answer:

   Hello -> Option B

4. Quick Check:

   Changing arr[0] changes first letter [OK]

Hint: Changing arr[0] changes first letter; output prints until '\0'. [OK]

Common Mistakes:

• Expecting output to be lowercase 'hello'
• Thinking only one character prints
• Assuming compilation error due to modification

4. Identify the error in the following code snippet:

char name[4] = "John";
std::cout << name << std::endl;

medium

A. Incorrect use of double quotes for character array.

B. Missing semicolon after declaration.

C. Array size is too small to hold the string and null terminator.

D. Cannot print character arrays with std::cout.

Solution

1. Step 1: Check array size vs string length

   The string "John" has 4 characters plus a null terminator, so it needs an array of size 5.

2. Step 2: Understand consequences of small array

   Declaring name[4] leaves no space for '\0', causing undefined behavior when printing.

3. Final Answer:

   Array size is too small to hold the string and null terminator. -> Option C

4. Quick Check:

   Array size must include space for '\0' [OK]

Hint: Always add 1 to string length for '\0' in array size. [OK]

Common Mistakes:

• Ignoring null terminator space
• Thinking printing char arrays is invalid
• Confusing syntax errors with size errors

5. You want to store the phrase "Hi!" in a character array and then replace the exclamation mark with a question mark. Which code correctly does this?

hard

A. char phrase[4] = "Hi!";
phrase[2] = '?';
std::cout << phrase << std::endl;

B. char phrase[3] = {'H', 'i', '?'};
std::cout << phrase << std::endl;

C. char phrase[4] = "Hi?";
phrase[3] = '!';
std::cout << phrase << std::endl;

D. char phrase[3] = "Hi!";
phrase[3] = '?';
std::cout << phrase << std::endl;

Solution

1. Step 1: Declare array with correct size for "Hi!"

   The phrase "Hi!" has 3 characters plus 1 for '\0', so array size must be 4.

2. Step 2: Replace '!' with '?' at correct index

   The '!' is at index 2, so phrase[2] = '?' correctly replaces it.

3. Step 3: Print the modified phrase

   Printing phrase outputs "Hi?" as expected.

4. Final Answer:

   char phrase[4] = "Hi!"; phrase[2] = '?'; std::cout << phrase << std::endl; -> Option A

5. Quick Check:

   Array size = 4; replace index 2 [OK]

Hint: Array size = chars + 1; replace character by index. [OK]

Common Mistakes:

• Using array size too small to hold string and '\0'
• Replacing wrong index character
• Confusing initialization with replacement