Dropping and clearing stashes in Git - Time & Space Complexity

Time Complexity: Dropping and clearing stashes

O(n) for git stash drop, O(1) for git stash clear

Understanding Time Complexity

We want to understand how the time to drop or clear stashes changes as the number of stashes grows.

How does git handle removing one or all stashes when there are many? Git stashes are stored in a reflog file for refs/stash.

Scenario Under Consideration

Analyze the time complexity of these git commands:

git stash drop stash@{2}
git stash clear

The first command removes a single stash by its index (rewriting reflog). The second removes all at once (deletes files).

Identify Repeating Operations

Look for repeated steps git must do internally.

• Primary operation: Drop: read entire reflog file (~n lines) and rewrite omitting one entry. Clear: delete two files (refs/stash and logs/refs/stash).
• How many times: Drop processes O(n) lines; clear is fixed file deletions.

How Execution Grows With Input

As the number of stashes (n) increases, the work changes like this:

Input Size (n)	Approx. Operations for drop	Approx. Operations for clear
10	About 10 read/write operations	Constant: 2 file deletes
100	About 100 read/write operations	Constant: 2 file deletes
1000	About 1000 read/write operations	Constant: 2 file deletes

Pattern observation: Dropping one stash grows linearly (reflog rewrite), clearing all stays constant.

Final Time Complexity

Time Complexity: O(n) for git stash drop, O(1) for git stash clear

Drop rewrites the O(n)-sized reflog file; clear just deletes files instantly.

Common Mistake

[X] Wrong: "Drop is O(1) since it targets one; clear is O(n) iterating all."

[OK] Correct: Reflog is a file; drop rewrites whole file O(n), clear deletes files O(1).

Interview Connect

Explaining git internals and why operations scale certain ways demonstrates systems thinking and tool expertise.

Self-Check

"If git used a database or linked structure for reflogs, how might complexities change? Why file-based?"