String Basics and Memory Representation in DSA C - Time & Space Complexity

Time Complexity: String Basics and Memory Representation

O(n)

Understanding Time Complexity

We want to understand how the time to work with strings grows as the string gets longer.

Specifically, how does reading or copying a string change when the string size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>
#include <string.h>

void copyString(char *dest, const char *src) {
    int i = 0;
    while (src[i] != '\0') {
        dest[i] = src[i];
        i++;
    }
    dest[i] = '\0';
}
    

This code copies a string from source to destination character by character until it reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying each character from source to destination.
• How many times: Once for every character in the string until the end character '\0'.

How Execution Grows With Input

As the string gets longer, the number of characters copied grows directly with its length.

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

Pattern observation: The work grows in a straight line with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to copy the string grows directly with the number of characters in the string.

Common Mistake

[X] Wrong: "Copying a string takes the same time no matter how long it is."

[OK] Correct: Each character must be copied one by one, so longer strings take more time.

Interview Connect

Understanding how string operations scale helps you reason about performance in real programs and shows you know how memory and loops work together.

Self-Check

"What if we used a built-in function like strcpy instead of a loop? How would the time complexity change?"