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?"

Practice

1. What does the LENGTH function do in PostgreSQL?

easy

A. Splits a string into an array

B. Finds the position of a substring inside a string

C. Converts a string to uppercase

D. Returns the number of characters in a string

Solution

1. Step 1: Understand LENGTH function purpose

   The LENGTH function counts how many characters are in a given string.

2. Step 2: Compare with other options

   POSITION finds substring location, UPPER changes case, SPLIT divides string. Only LENGTH counts characters.

3. Final Answer:

   Returns the number of characters in a string -> Option D

4. Quick Check:

   LENGTH = character count [OK]

Hint: LENGTH counts characters, POSITION finds substring start [OK]

Common Mistakes:

• Confusing LENGTH with POSITION
• Thinking LENGTH changes string case
• Assuming LENGTH splits strings

2. Which of the following is the correct syntax to find the position of substring 'cat' in string 'concatenate' using PostgreSQL?

easy

A. LENGTH('cat' IN 'concatenate')

B. POSITION('concatenate' IN 'cat')

C. POSITION('cat' IN 'concatenate')

D. FIND('cat', 'concatenate')

Solution

1. Step 1: Recall POSITION syntax

   POSITION(substring IN string) finds where substring starts in string.

2. Step 2: Check each option

   POSITION('cat' IN 'concatenate') matches syntax. POSITION('concatenate' IN 'cat') reverses arguments. LENGTH('cat' IN 'concatenate') uses LENGTH wrongly. FIND('cat', 'concatenate') uses non-existent FIND function.

3. Final Answer:

   POSITION('cat' IN 'concatenate') -> Option C

4. Quick Check:

   POSITION(substring IN string) correct syntax [OK]

Hint: Use POSITION('sub' IN 'string') to find substring start [OK]

Common Mistakes:

• Swapping substring and string arguments
• Using LENGTH instead of POSITION
• Using non-PostgreSQL functions like FIND

3. What is the result of this query?

SELECT POSITION('day' IN 'holiday') AS pos, LENGTH('holiday') AS len;

medium

A. pos = 4, len = 7

B. pos = 5, len = 7

C. pos = 0, len = 7

D. pos = 4, len = 6

Solution

1. Step 1: Find POSITION of 'day' in 'holiday'

   'holiday' positions: 1:'h', 2:'o', 3:'l', 4:'i', 5:'d', 6:'a', 7:'y'. 'day' matches positions 5('d')-6('a')-7('y'), so starts at 5 (1-based).

2. Step 2: Calculate LENGTH of 'holiday'

   'holiday' has 7 characters.

3. Final Answer:

   pos = 5, len = 7 -> Option B

4. Quick Check:

   POSITION('day' IN 'holiday') = 5, LENGTH('holiday') = 7 [OK]

Hint: Count characters carefully; POSITION is 1-based [OK]

Common Mistakes:

• Counting POSITION starting at 0
• Miscounting substring start
• Confusing LENGTH with POSITION

4. Identify the error in this query:

SELECT POSITION('test', 'contest') AS pos;

medium

A. Uses comma instead of IN keyword in POSITION function

B. Missing AS keyword for alias

C. POSITION does not accept string literals

D. Syntax is correct, no error

Solution

1. Step 1: Check POSITION function syntax

   POSITION requires syntax POSITION(substring IN string), not POSITION(substring, string).

2. Step 2: Identify error in query

   The query uses comma instead of IN keyword, causing syntax error.

3. Final Answer:

   Uses comma instead of IN keyword in POSITION function -> Option A

4. Quick Check:

   POSITION(substring IN string) correct syntax [OK]

Hint: Use IN keyword, not comma, in POSITION function [OK]

Common Mistakes:

• Using comma instead of IN in POSITION
• Assuming alias AS is mandatory (it's optional)
• Thinking POSITION can't use string literals

5. You want to find the position of the first space character in the string 'Find the position'. Which query will correctly return this position?

hard

A. SELECT POSITION(' ' IN 'Find the position');

B. SELECT LENGTH(' ' IN 'Find the position');

C. SELECT POSITION('space' IN 'Find the position');

D. SELECT POSITION(' ' FROM 'Find the position');

Solution

1. Step 1: Identify correct function usage for substring position

   POSITION(substring IN string) finds where substring starts. We want the space character ' '.

2. Step 2: Evaluate each option

   SELECT POSITION(' ' IN 'Find the position'); uses correct syntax and substring. SELECT LENGTH(' ' IN 'Find the position'); uses LENGTH wrongly. SELECT POSITION('space' IN 'Find the position'); searches for word 'space' which is not present. SELECT POSITION(' ' FROM 'Find the position'); uses FROM instead of IN, which is invalid syntax.

3. Final Answer:

   SELECT POSITION(' ' IN 'Find the position'); -> Option A

4. Quick Check:

   POSITION(' ' IN string) finds first space [OK]

Hint: Use POSITION(' ' IN string) to find first space [OK]

Common Mistakes:

• Using LENGTH instead of POSITION
• Searching for word 'space' instead of character
• Using FROM instead of IN in POSITION