String length and membership test in Python - Time & Space Complexity

Time Complexity: String length and membership test

O(n)

Understanding Time Complexity

We want to understand how long it takes to check the length of a string and to see if a character is inside it.

How does the time needed change when the string gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_string = "hello world"
length = len(my_string)
if 'w' in my_string:
    print("Found 'w'!")
else:
    print("'w' not found.")

This code gets the length of a string and checks if the letter 'w' is inside it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each character to find 'w' in the string.
• How many times: Up to once for each character until 'w' is found or the end is reached.

How Execution Grows With Input

As the string gets longer, checking for 'w' may take longer because it might look at more characters.

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

Pattern observation: The number of checks grows directly with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check membership grows in a straight line as the string gets longer.

Common Mistake

[X] Wrong: "Checking if a character is in a string always takes the same time, no matter the string size."

[OK] Correct: The check may need to look at many characters, so longer strings usually take more time.

Interview Connect

Knowing how string operations grow with size helps you write clear and efficient code, a skill that shows your understanding of how programs work behind the scenes.

Self-Check

"What if we checked for a substring instead of a single character? How would the time complexity change?"