Bird
Raised Fist0
Gitdevops~5 mins

Searching history with git log -S - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: Searching history with git log -S
O(n)
Understanding Time Complexity

When we search for changes in a Git repository using git log -S, we want to know how the time it takes grows as the project history grows.

We ask: How does searching for a string in commit history scale with more commits?

Scenario Under Consideration

Analyze the time complexity of this Git command:

git log -S "search_string" --source --all

This command searches all commits for changes that add or remove the exact string "search_string".

Identify Repeating Operations

Look at what repeats when running this command:

  • Primary operation: Git examines each commit's changes to find the string.
  • How many times: Once for every commit in the repository history.
How Execution Grows With Input

As the number of commits grows, Git checks each commit one by one for the string.

Input Size (n)Approx. Operations
10 commits10 checks
100 commits100 checks
1000 commits1000 checks

Pattern observation: The work grows directly with the number of commits.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows in a straight line as the commit count increases.

Common Mistake

[X] Wrong: "Git searches only the latest commits, so time stays the same no matter how many commits exist."

[OK] Correct: Git actually checks every commit in the history to find changes with the string, so more commits mean more work.

Interview Connect

Understanding how Git searches history helps you explain how tools handle large data and why some commands slow down as projects grow. This skill shows you think about efficiency in real work.

Self-Check

What if we limited the search to a single branch instead of all commits? How would the time complexity change?

Practice

(1/5)
1. What does the git log -S command do?
easy
A. Finds commits that added or removed a specific string in the code.
B. Shows the current status of files in the working directory.
C. Displays the list of branches in the repository.
D. Creates a new branch with the given name.

Solution

  1. Step 1: Understand the purpose of git log -S

    This command searches commit history for changes that added or removed a specific string.

  2. Step 2: Compare with other git commands

    Other options like git status show file status, git branch lists branches, and git branch <name> creates branches, which are different tasks.

  3. Final Answer:

    Finds commits that added or removed a specific string in the code. -> Option A

  4. Quick Check:

    Search commits by string change = B [OK]
Hint: Remember: -S searches for string changes in commits [OK]
Common Mistakes:
  • Confusing -S with showing file status
  • Thinking it lists branches
  • Assuming it creates branches
2. Which of the following is the correct syntax to find commits that added or removed the word fix using git log -S?
easy
A. git log -S fix
B. git log -s fix
C. git log --search=fix
D. git log -search fix

Solution

  1. Step 1: Identify correct option flag

    The correct flag to search for string changes is uppercase -S, so git log -S fix is correct.

  2. Step 2: Check other options for syntax errors

    -s is not valid for this purpose, and --search or -search are not valid git log options.

  3. Final Answer:

    git log -S fix -> Option A

  4. Quick Check:

    Uppercase -S for string search = A [OK]
Hint: Use uppercase -S to search string changes in git log [OK]
Common Mistakes:
  • Using lowercase -s instead of -S
  • Trying non-existent --search option
  • Adding extra dashes incorrectly
3. Given the following git log command:
git log -S 'bugfix' --oneline
What will this command output?
medium
A. An error because the string 'bugfix' is not quoted correctly.
B. A list of all commits with the word 'bugfix' anywhere in the commit message.
C. A list of commits that modified files named 'bugfix'.
D. A list of commits that added or removed the string 'bugfix', shown in one line each.

Solution

  1. Step 1: Understand -S 'bugfix' usage

    This searches commits that added or removed the exact string 'bugfix' in the code or content.

  2. Step 2: Understand --oneline option

    This shows each commit in a short single line format for easy reading.

  3. Final Answer:

    A list of commits that added or removed the string 'bugfix', shown in one line each. -> Option D

  4. Quick Check:

    -S finds string changes, --oneline shortens output = D [OK]
Hint: Combine -S with --oneline for short commit list by string [OK]
Common Mistakes:
  • Thinking it searches commit messages instead of code changes
  • Assuming it filters by file names
  • Believing quotes cause errors here
4. You run git log -S 'update' but get no results, even though you know the word 'update' was added in some commits. What could be the problem?
medium
A. You need to use git log -G 'update' to search commit messages.
B. You forgot to put quotes around the search string.
C. The string 'update' was only changed in commit messages, not in code.
D. The repository has no commits at all.

Solution

  1. Step 1: Understand what -S searches

    -S searches for string changes in the code or content, not in commit messages.

  2. Step 2: Consider commit message search

    If 'update' was only added or changed in commit messages, -S won't find it; use git log --grep 'update' to search commit messages. -G searches code diffs by regex.

  3. Final Answer:

    The string 'update' was only changed in commit messages, not in code. -> Option C

  4. Quick Check:

    -S searches code changes, not commit messages = A [OK]
Hint: Use -G to search commit messages, -S for code changes [OK]
Common Mistakes:
  • Assuming -S searches commit messages
  • Thinking quotes cause no results
  • Believing repository is empty without checking
5. You want to find all commits that added or removed the string TODO but only in the src/ folder. Which command will do this correctly?
hard
A. git log -S 'TODO' --path src/
B. git log -S 'TODO' -- src/
C. git log -S 'TODO' src/
D. git log --S 'TODO' -- src/

Solution

  1. Step 1: Use -S 'TODO' to search string changes

    This finds commits adding or removing 'TODO'.

  2. Step 2: Use -- src/ to limit search to the src folder

    The double dash -- separates options from path arguments, so -- src/ limits the search to that folder.

  3. Step 3: Check other options for syntax correctness

    src/ alone without -- is invalid here; --path is not a git log option; --S is invalid (uppercase S must be after git log).

  4. Final Answer:

    git log -S 'TODO' -- src/ -> Option B

  5. Quick Check:

    Use -- before path to limit git log search = C [OK]
Hint: Use -- before folder path to limit git log search [OK]
Common Mistakes:
  • Omitting -- before path
  • Using invalid --path option
  • Writing --S instead of -S