PRIMARY KEY and SERIAL behavior in PostgreSQL - Time & Space Complexity

Time Complexity: PRIMARY KEY and SERIAL behavior

O(log n)

Understanding Time Complexity

We want to understand how the time to insert rows grows when using PRIMARY KEY with SERIAL in PostgreSQL.

How does the database handle generating unique keys and checking for duplicates as data grows?

Scenario Under Consideration

Analyze the time complexity of inserting rows with a SERIAL primary key.

CREATE TABLE users (
  id SERIAL PRIMARY KEY,
  name TEXT
);

INSERT INTO users (name) VALUES ('Alice');
INSERT INTO users (name) VALUES ('Bob');
-- Repeated inserts as table grows
    

This code creates a table where the id is automatically assigned and unique, then inserts rows one by one.

Identify Repeating Operations

Look at what repeats when inserting many rows.

• Primary operation: Generating a new unique id and inserting it into the primary key index.
• How many times: Once per insert, repeated for each new row.

How Execution Grows With Input

As the number of rows grows, the database must keep the primary key index updated.

Input Size (n)	Approx. Operations
10	About 10 index insertions
100	About 100 index insertions
1000	About 1000 index insertions

Pattern observation: Each new row requires updating the index, which grows with the number of rows.

Final Time Complexity

Time Complexity: O(log n) per insert

This means each insert takes a bit more time as the table grows, but the increase is slow and manageable.

Common Mistake

[X] Wrong: "Inserting with SERIAL primary key is always constant time, no matter how big the table is."

[OK] Correct: The database must update a tree-like index to keep keys unique, which takes more steps as the table grows, so insert time grows slowly.

Interview Connect

Understanding how indexes affect insert speed helps you explain database performance clearly and shows you know how data structures work behind the scenes.

Self-Check

"What if we removed the PRIMARY KEY constraint and just used SERIAL without an index? How would the time complexity of inserts change?"