Squashing commits in Git - Time & Space Complexity

Time Complexity: Squashing commits

O(n)

Understanding Time Complexity

When we squash commits in git, we combine multiple changes into one. Understanding how the time to squash grows helps us know what to expect as the number of commits increases.

We want to answer: How does the effort to squash commits change as we have more commits?

Scenario Under Consideration

Analyze the time complexity of the following git commands used to squash commits.

git rebase -i HEAD~5
# In the editor, mark commits to squash
# Save and close editor
# Git rewrites commit history combining commits

This snippet shows an interactive rebase to squash the last 5 commits into one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Git processes each commit in the range one by one during the rebase.
• How many times: Once per commit in the selected range (e.g., 5 commits means 5 steps).

How Execution Grows With Input

As the number of commits to squash increases, git must process each commit individually to combine them.

Input Size (n)	Approx. Operations
10 commits	Processes 10 commits sequentially
100 commits	Processes 100 commits sequentially
1000 commits	Processes 1000 commits sequentially

Pattern observation: The work grows directly with the number of commits; doubling commits roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to squash commits grows linearly with the number of commits involved.

Common Mistake

[X] Wrong: "Squashing many commits takes the same time as squashing just a few."

[OK] Correct: Each commit must be processed, so more commits mean more work and more time.

Interview Connect

Understanding how git operations scale with input size shows you can think about tool efficiency and plan work better. This skill helps you explain your choices clearly in real projects.

Self-Check

What if we changed from squashing commits interactively to using a single merge commit? How would the time complexity change?

Practice

1. What is the main purpose of squashing commits in Git?

easy

A. To revert the last commit without changing history

B. To combine multiple commits into one for a cleaner history

C. To create a new branch from the current commit

D. To delete all commits from the repository

Solution

1. Step 1: Understand commit history management

   Squashing is used to combine several commits into a single commit to simplify the commit history.

2. Step 2: Identify the purpose of squashing

   This helps keep the project history clean and easier to read by reducing clutter from many small commits.

3. Final Answer:

   To combine multiple commits into one for a cleaner history -> Option B

4. Quick Check:

   Squashing = combine commits [OK]

Hint: Squash = combine commits to clean history [OK]

Common Mistakes:

• Thinking squashing deletes commits permanently
• Confusing squashing with branching
• Believing squashing reverts commits

2. Which Git command starts an interactive rebase to squash commits?

easy

A. git commit --squash HEAD~3

B. git merge -i HEAD~3

C. git rebase -i HEAD~3

D. git reset --soft HEAD~3

Solution

1. Step 1: Identify the command for interactive rebase

   The command to start an interactive rebase is git rebase -i followed by the commit range.

2. Step 2: Confirm the correct syntax

   git rebase -i HEAD~3 opens the last 3 commits for editing, allowing squashing.

3. Final Answer:

   git rebase -i HEAD~3 -> Option C

4. Quick Check:

   Interactive rebase = git rebase -i [OK]

Hint: Use git rebase -i to start squashing commits [OK]

Common Mistakes:

• Using git merge -i which does not exist
• Trying git commit --squash which is invalid
• Confusing reset with rebase for squashing

3. Given these commits:

commit1: Add README
commit2: Fix typo
commit3: Update README formatting

If you run git rebase -i HEAD~3 and squash commit2 and commit3 into commit1, what will the commit history show?

medium

A. One commit combining messages from commit1, commit2, and commit3

B. Three separate commits unchanged

C. One commit with message from commit1 only

D. Two commits: commit1 and combined commit2+commit3

Solution

1. Step 1: Understand squash behavior in interactive rebase

   Squashing merges commits into one, combining their changes and commit messages.

2. Step 2: Result of squashing commit2 and commit3 into commit1

   The final commit will include all changes and combined commit messages from all three commits.

3. Final Answer:

   One commit combining messages from commit1, commit2, and commit3 -> Option A

4. Quick Check:

   Squash merges commits and messages [OK]

Hint: Squash merges commits and their messages together [OK]

Common Mistakes:

• Assuming only the first commit message remains
• Expecting commits to stay separate after squash
• Thinking squash deletes commit messages

4. You ran git rebase -i HEAD~4 to squash commits but got a conflict error. What should you do next?

medium

A. Manually fix the conflicts, then run git rebase --continue

B. Abort the rebase with git rebase --abort and try again

C. Run git reset --hard to discard all changes

D. Push your changes immediately to remote to fix conflicts

Solution

1. Step 1: Understand conflict during rebase

   A conflict means Git needs you to fix code differences manually before continuing.

2. Step 2: Resolve conflicts and continue rebase

   Fix the conflicts in files, then run git rebase --continue to proceed with squashing.

3. Final Answer:

   Manually fix the conflicts, then run git rebase --continue -> Option A

4. Quick Check:

   Fix conflicts + git rebase --continue [OK]

Hint: Fix conflicts manually then git rebase --continue [OK]

Common Mistakes:

• Aborting rebase without trying to fix conflicts
• Using git reset --hard which discards work
• Pushing incomplete changes to remote

5. You squashed commits locally and want to update the remote branch. What is the correct command to push your changes safely?

hard

A. git push --all origin

B. git push origin main

C. git push --no-verify origin main

D. git push --force-with-lease origin main

Solution

1. Step 1: Understand effect of squashing on commit history

   Squashing rewrites commit history, so the remote branch history differs from local.

2. Step 2: Use force push safely

   To update remote with rewritten history, use git push --force-with-lease to avoid overwriting others' work accidentally.

3. Final Answer:

   git push --force-with-lease origin main -> Option D

4. Quick Check:

   Force push safely after squash [OK]

Hint: Use git push --force-with-lease after squash [OK]

Common Mistakes:

• Using normal git push causing rejection
• Using --no-verify which skips hooks but not force push
• Pushing all branches unnecessarily