Time Complexity: git log formatting options
O(n)
0
0
git log formatting options - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to run git log with formatting options changes as the number of commits grows.
How does adding more commits affect the work done when formatting the log output?
Scenario Under Consideration
Analyze the time complexity of the following git command.
git log --pretty=format:"%h - %an, %ar : %s"This command lists commit history with a custom format showing short hash, author name, relative date, and commit message.
Identify Repeating Operations
Look for repeated actions in the command.
- Primary operation: Formatting each commit's data into the specified string.
- How many times: Once for every commit in the history being shown.
How Execution Grows With Input
As the number of commits increases, the command formats each commit one by one.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 formatting operations |
| 100 | 100 formatting operations |
| 1000 | 1000 formatting operations |
Pattern observation: The work grows directly with the number of commits; doubling commits doubles the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to format the log grows linearly with the number of commits shown.
Common Mistake
[X] Wrong: "Formatting the log output is instant no matter how many commits there are."
[OK] Correct: Each commit must be processed and formatted, so more commits mean more work and more time.
Interview Connect
Understanding how commands scale with input size helps you write efficient scripts and troubleshoot performance in real projects.
Self-Check
"What if we add a filter to show only commits by one author? How would the time complexity change?"