Replication basics in MySQL - Time & Space Complexity

Time Complexity: Replication basics

O(n)

Understanding Time Complexity

When using replication in MySQL, it's important to understand how the process scales as data changes grow.

We want to know how the time to copy data from one server to another changes as the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of this simple replication setup.

-- On master server
CREATE TABLE orders (id INT PRIMARY KEY, details TEXT);

-- Insert many rows
INSERT INTO orders VALUES (1, 'details1'), (2, 'details2');

-- On slave server
START SLAVE;
-- Slave reads and applies changes from master
    

This code shows a master server with a table and inserts, and a slave server that reads and applies these changes.

Identify Repeating Operations

Look at what repeats during replication.

• Primary operation: The slave reads each change (insert/update/delete) from the master's log and applies it.
• How many times: Once for every change made on the master.

How Execution Grows With Input

As the number of changes on the master grows, the slave has more work to do.

Input Size (n)	Approx. Operations
10 changes	10 apply operations
100 changes	100 apply operations
1000 changes	1000 apply operations

Pattern observation: The work grows directly with the number of changes to replicate.

Final Time Complexity

Time Complexity: O(n)

This means the time to replicate grows in a straight line with the number of changes made on the master.

Common Mistake

[X] Wrong: "Replication time stays the same no matter how many changes happen."

[OK] Correct: Each change must be copied and applied, so more changes mean more work and more time.

Interview Connect

Understanding how replication time grows helps you design systems that stay fast as data grows, a key skill in real projects.

Self-Check

"What if the slave applied changes in batches instead of one by one? How would the time complexity change?"