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