String length and position functions in PostgreSQL - Time & Space Complexity

Time Complexity: String length and position functions

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the length of a string or the position of a substring inside it.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT LENGTH(text_column) AS str_length,
       POSITION('abc' IN text_column) AS pos_abc
FROM example_table;
    

This code finds the length of each string and the position of 'abc' inside it for every row.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning characters in the string to find substring (POSITION). LENGTH is O(1) using stored length.
• How many times: Up to O(n) for POSITION; O(1) for LENGTH.

How Execution Grows With Input

As the string gets longer, the time to search for substring grows roughly in direct proportion. (LENGTH is O(1))

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

Pattern observation: The work grows steadily as the string length increases.

Final Time Complexity

Time Complexity: O(n)

This means the time for POSITION grows linearly with the string size (LENGTH is O(1)).

Common Mistake

[X] Wrong: "Finding the position is instant no matter how long the string is."

[OK] Correct: The database must scan characters to search, so longer strings take more time. (LENGTH is O(1))

Interview Connect

Knowing how string functions scale helps you write efficient queries and understand performance when working with text data.

Self-Check

"What if we searched for a substring that appears near the end of the string? How would the time complexity change?"