Common string operations - Time & Space Complexity

Time Complexity: Common string operations

O(n)

Understanding Time Complexity

When working with strings in C, it's important to know how the time it takes to run your code changes as the string gets longer.

We want to find out how common string operations grow in cost as the input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string.h>

int length = strlen(str);
char dest[100];
strcpy(dest, str);
int cmp = strcmp(str, dest);
    

This code finds the length of a string, copies it to another array, and then compares the two strings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each function (strlen, strcpy, strcmp) loops through the string characters one by one.
• How many times: Each function runs once, but each checks characters until it finds the string end.

How Execution Grows With Input

As the string gets longer, each operation takes more steps because it looks at every character.

Input Size (n)	Approx. Operations
10	About 10 steps per operation
100	About 100 steps per operation
1000	About 1000 steps per operation

Pattern observation: The work grows directly with the string length; double the length, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these string operations grows in a straight line with the string size.

Common Mistake

[X] Wrong: "String functions like strlen or strcpy run in constant time because they just look at the string once."

[OK] Correct: These functions actually check each character until they find the end, so their time depends on string length.

Interview Connect

Understanding how string operations scale helps you write efficient code and answer questions about performance clearly.

Self-Check

"What if we used a function that only checked the first 5 characters of a string? How would the time complexity change?"

Practice

1. Which C function is used to find the length of a string?

easy

A. strlen

B. strcpy

C. strcmp

D. strcat

Solution

1. Step 1: Understand string length concept

   The length of a string is the number of characters before the null terminator.

2. Step 2: Identify the correct function

   strlen returns the length of a string, while strcpy copies, strcmp compares, and strcat concatenates strings.

3. Final Answer:

   strlen -> Option A

4. Quick Check:

   Length function = strlen [OK]

Hint: Remember: length = strlen, copy = strcpy [OK]

Common Mistakes:

• Confusing strcpy with strlen
• Using strcmp to get length
• Thinking strcat returns length

2. Which of the following is the correct syntax to copy string src into dest in C?

easy

A. strcat(dest, src);

B. strcpy(src, dest);

C. strlen(dest, src);

D. strcpy(dest, src);

Solution

1. Step 1: Understand strcpy parameters

   strcpy copies the source string into the destination string. The first argument is destination, second is source.

2. Step 2: Check each option

   strcpy(dest, src); uses correct order (destination first, source second). strcpy(src, dest); reverses parameters. strcat(dest, src); concatenates strings. strlen(dest, src); returns length, not copies.

3. Final Answer:

   strcpy(dest, src); -> Option D

4. Quick Check:

   Copy syntax = strcpy(dest, src) [OK]

Hint: Copy: destination first, source second in strcpy [OK]

Common Mistakes:

• Swapping source and destination arguments
• Using strcat instead of strcpy for copying
• Using strlen for copying strings

3. What is the output of this C code?

char str1[20] = "Hello, ";
char str2[] = "World!";
strcat(str1, str2);
printf("%s", str1);

medium

A. Hello,

B. World!Hello,

C. Hello, World!

D. Compilation error

Solution

1. Step 1: Understand strcat behavior

   strcat appends the second string to the end of the first string.

2. Step 2: Apply strcat to given strings

   Appending "World!" to "Hello, " results in "Hello, World!" stored in str1.

3. Final Answer:

   Hello, World! -> Option C

4. Quick Check:

   Concatenate str1 + str2 = Hello, World! [OK]

Hint: strcat adds second string to end of first [OK]

Common Mistakes:

• Expecting strcat to replace string
• Confusing order of concatenation
• Assuming strcat returns new string

4. Identify the error in this code snippet:

char s1[5] = "Hello";
char s2[10];
strcpy(s2, s1);
printf("%s", s2);

medium

A. s2 array size is too small for copy

B. s1 array size is too small for "Hello"

C. strcpy parameters are reversed

D. Missing null terminator in s2

Solution

1. Step 1: Check array size for s1

   String "Hello" has 5 characters plus 1 for '\0' terminator, so s1 needs size at least 6.

2. Step 2: Analyze s1 declaration

   s1 is declared with size 5, which is too small to hold "Hello" plus null terminator, causing overflow.

3. Final Answer:

   s1 array size is too small for "Hello" -> Option B

4. Quick Check:

   String size must include '\0' [OK]

Hint: String size must fit characters + '\0' terminator [OK]

Common Mistakes:

• Ignoring null terminator size
• Assuming strcpy reverses parameters
• Thinking s2 size is too small here

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

char text[] = "Programming in C";
char *ptr = strstr(text, "in");
printf("%s", ptr);

hard

A. in C

B. Programming in C

C. in

D. NULL

Solution

1. Step 1: Understand strstr function

   strstr returns pointer to first occurrence of substring or NULL if not found.

2. Step 2: Find substring "in" in text

   "in" first appears inside "Programming in C" starting at "in C" substring.

3. Step 3: Print from pointer

   Printing from pointer prints "in C" including the substring and rest of string.

4. Final Answer:

   in C -> Option A

5. Quick Check:

   strstr returns substring start pointer [OK]

Hint: strstr returns pointer to substring start [OK]

Common Mistakes:

• Expecting strstr to return only substring
• Confusing strstr with strcmp
• Assuming strstr returns NULL if substring found