Time Complexity: Lock types (shared, exclusive)
O(n)
0
0
Lock types (shared, exclusive) in MySQL - Time & Space Complexity
Understanding Time Complexity
When databases use locks, they control how many users can access data at the same time.
We want to understand how the time to get and release locks changes as more users try to access the data.
Scenario Under Consideration
Analyze the time complexity of acquiring shared and exclusive locks in MySQL.
-- Transaction 1 requests a shared lock
LOCK TABLES orders READ;
-- Transaction 2 requests an exclusive lock
LOCK TABLES orders WRITE;
-- Transaction 1 releases lock
UNLOCK TABLES;
-- Transaction 2 acquires exclusive lock after Transaction 1
LOCK TABLES orders WRITE;
This code shows two transactions trying to lock the same table with different lock types.
Identify Repeating Operations
Locks are requested and released repeatedly as transactions run.
- Primary operation: Checking and waiting for lock availability.
- How many times: Once per lock request, but can repeat if waiting.
How Execution Grows With Input
As more transactions request locks, waiting time can increase.
| Number of Transactions (n) | Approx. Lock Wait Checks |
|---|---|
| 10 | Up to 10 checks |
| 100 | Up to 100 checks |
| 1000 | Up to 1000 checks |
Pattern observation: The time to get a lock grows roughly in direct proportion to the number of transactions waiting.
Final Time Complexity
Time Complexity: O(n)
This means the time to acquire a lock grows linearly as more transactions try to lock the same resource.
Common Mistake
[X] Wrong: "Locks always happen instantly, no matter how many users wait."
[OK] Correct: When many transactions wait, each must check and wait their turn, so time grows with the number of waiters.
Interview Connect
Understanding how locks affect performance helps you explain database behavior clearly and shows you know how systems handle multiple users safely.
Self-Check
"What if we changed from table-level locks to row-level locks? How would the time complexity change?"