Time Complexity: Why rebasing creates linear history
O(n)
0
0
Why rebasing creates linear history in Git - Performance Analysis
Understanding Time Complexity
We want to understand how the work done by git rebasing changes as the number of commits grows.
Specifically, how does rebasing create a straight line of commits instead of a branching tree?
Scenario Under Consideration
Analyze the time complexity of this git rebase command sequence.
git checkout feature
# feature branch has commits: C1 - C2 - C3
git rebase main
# main branch has commits: M1 - M2
# rebase applies C1, C2, C3 on top of M2
This code moves each commit from the feature branch to be based on the latest main branch commit, creating a linear history.
Identify Repeating Operations
Look for repeated steps in the rebase process.
- Primary operation: Applying each commit from the feature branch one by one onto the main branch.
- How many times: Once for each commit in the feature branch (e.g., 3 times for C1, C2, C3).
How Execution Grows With Input
As the number of commits on the feature branch increases, the rebase applies each commit in order.
| Input Size (n commits) | Approx. Operations (commit applications) |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
Pattern observation: The work grows directly with the number of commits to rebase.
Final Time Complexity
Time Complexity: O(n)
This means the time to rebase grows in a straight line as you add more commits to move.
Common Mistake
[X] Wrong: "Rebasing instantly rewrites all commits at once without extra work per commit."
[OK] Correct: Each commit must be reapplied one by one, so the work adds up with more commits.
Interview Connect
Understanding how rebasing scales helps you explain why it creates a clean, straight history and what happens behind the scenes.
Self-Check
What if we changed rebase to merge? How would the time complexity and history shape change?