String handling using library functions - Time & Space Complexity

Time Complexity: String handling using library functions

O(n)

Understanding Time Complexity

When using library functions for strings, it's important to know how the time to run grows as the string gets longer.

We want to see how the work changes when the input string size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string.h>

int main() {
    char str1[] = "hello world";
    char str2[20];
    strcpy(str2, str1);
    int len = strlen(str2);
    return 0;
}
    

This code copies one string to another and then finds the length of the copied string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The functions strcpy and strlen both scan the string character by character.
• How many times: Each function goes through the string until it finds the end (the null character).

How Execution Grows With Input

As the string gets longer, both copying and measuring length take more steps, roughly one step per character.

Input Size (n)	Approx. Operations
10	About 20 steps (10 for copy + 10 for length)
100	About 200 steps
1000	About 2000 steps

Pattern observation: The total work grows roughly twice as fast as the string length because two passes happen.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly with the length of the string.

Common Mistake

[X] Wrong: "Using library functions like strcpy or strlen is always constant time because they are built-in."

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

Interview Connect

Understanding how string functions work helps you explain your code clearly and shows you know what happens behind the scenes.

Self-Check

"What if we used strcat to append one string to another? How would the time complexity change?"

Practice

1. Which library function in C is used to find the length of a string (excluding the null character)?

easy

A. strcpy()

B. strcat()

C. strcmp()

D. strlen()

Solution

1. Step 1: Understand the purpose of strlen()

   The function strlen() counts characters in a string until it reaches the null terminator '\0', giving the string length.

2. Step 2: Compare with other functions

   strcpy() copies strings, strcmp() compares strings, strcat() concatenates strings, so they do not measure length.

3. Final Answer:

   strlen() -> Option D

4. Quick Check:

   Length function = strlen() [OK]

Hint: Length means count chars before '\0', use strlen() [OK]

Common Mistakes:

• Confusing strcpy() with strlen()
• Using strcmp() to get length
• Forgetting null terminator in length count

2. Which of the following is the correct syntax to copy string src into dest using a standard library function?

easy

A. strcpy(src, dest);

B. strcpy(dest, src);

C. strcpy(dest);

D. strcpy(src);

Solution

1. Step 1: Recall strcpy() function signature

   strcpy() takes two arguments: destination string first, then source string to copy from.

2. Step 2: Check each option

   Only strcpy(dest, src); matches the correct order and argument count.

3. Final Answer:

   strcpy(dest, src); -> Option B

4. Quick Check:

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

Hint: Destination first, source second in strcpy() [OK]

Common Mistakes:

• Swapping source and destination arguments
• Using only one argument
• Missing semicolon or parentheses

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

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

int main() {
    char str1[20] = "Hello";
    char str2[] = "World";
    strcat(str1, str2);
    printf("%s", str1);
    return 0;
}

medium

A. HelloWorld

B. Hello World

C. WorldHello

D. Hello

Solution

1. Step 1: Understand strcat() behavior

   strcat() appends the second string to the end of the first string without adding spaces.

2. Step 2: Analyze the code output

   str1 starts as "Hello", str2 is "World". After strcat(str1, str2), str1 becomes "HelloWorld".

3. Final Answer:

   HelloWorld -> Option A

4. Quick Check:

   Concatenate without space = HelloWorld [OK]

Hint: strcat joins strings directly, no spaces added [OK]

Common Mistakes:

• Expecting a space between strings
• Confusing strcat() with strcpy()
• Not allocating enough space in destination

4. Identify the error in the following code snippet:

#include <string.h>

int main() {
    char s1[5] = "Data";
    char s2[] = "Science";
    strcat(s1, s2);
    return 0;
}

medium

A. Missing #include <stdio.h>

B. strcat() syntax is incorrect

C. s1 array size is too small for concatenation

D. s2 should be declared as char *s2

Solution

1. Step 1: Check array sizes for strcat()

   s1 has size 5, holding "Data" plus '\0'. Concatenating "Science" (7 chars) will overflow s1.

2. Step 2: Verify other options

   strcat() syntax is correct, #include <stdio.h> is not mandatory here, and s2 declaration is valid as array.

3. Final Answer:

   s1 array size is too small for concatenation -> Option C

4. Quick Check:

   Buffer overflow risk = s1 too small [OK]

Hint: Destination array must fit combined strings [OK]

Common Mistakes:

• Ignoring buffer size for strcat()
• Assuming strcat() adds space automatically
• Confusing array and pointer declarations

5. Given two strings char s1[] = "apple"; and char s2[] = "apricot";, which library function call correctly checks if s1 comes before s2 in dictionary order?

hard

A. strcmp(s1, s2) < 0

B. strcmp(s1, s2) > 0

C. strcmp(s2, s1) < 0

D. strcmp(s2, s1) > 0

Solution

1. Step 1: Understand strcmp() return values

   strcmp() returns a negative value if first string is lexicographically less than second, zero if equal, positive if greater.

2. Step 2: Apply to given strings

   "apple" comes before "apricot", so strcmp(s1, s2) returns negative, meaning strcmp(s1, s2) < 0 is true.

3. Final Answer:

   strcmp(s1, s2) < 0 -> Option A

4. Quick Check:

   Lex order check = strcmp(s1, s2) < 0 [OK]

Hint: strcmp() negative means first string is before second [OK]

Common Mistakes:

• Reversing argument order in strcmp()
• Checking for > 0 instead of < 0
• Assuming strcmp() returns boolean