Repository (committed history) in Git - Time & Space Complexity

Time Complexity: Repository (committed history)

O(n)

Understanding Time Complexity

When working with a git repository, it's important to understand how the time to access committed history changes as the repository grows.

We want to know how the cost of viewing or searching commits grows when more commits are added.

Scenario Under Consideration

Analyze the time complexity of the following git command.

git log --oneline

This command lists all commits in the repository in a short form, showing the commit history.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each commit object in the history one by one.
• How many times: Once for every commit in the repository.

How Execution Grows With Input

As the number of commits increases, the time to list them grows proportionally.

Input Size (n)	Approx. Operations
10 commits	10 operations (reading each commit)
100 commits	100 operations
1000 commits	1000 operations

Pattern observation: The time grows linearly as the number of commits increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to list commits grows directly with the number of commits in the repository.

Common Mistake

[X] Wrong: "Listing commits is always fast no matter how many commits exist."

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

Interview Connect

Understanding how git commands scale with repository size helps you work efficiently and explain your reasoning clearly in technical discussions.

Self-Check

"What if we used a command to show only the last 10 commits? How would the time complexity change?"

Practice

1. What does the git log command show in a Git repository?

easy

A. A list of all commits made in the repository history

B. The current status of files in the working directory

C. The list of branches in the repository

D. The remote repository URLs configured

Solution

1. Step 1: Understand the purpose of git log

   The git log command is designed to show the commit history of the repository, listing all saved changes.

2. Step 2: Differentiate from other commands

   Commands like git status show file changes, git branch shows branches, and git remote -v shows remote URLs, not commit history.

3. Final Answer:

   A list of all commits made in the repository history -> Option A

4. Quick Check:

   Commit history = git log output [OK]

Hint: Remember: git log = commit history list [OK]

Common Mistakes:

• Confusing git log with git status
• Thinking git log shows branches
• Mixing git log with remote info commands

2. Which of the following commands correctly shows a short, one-line summary of each commit in the history?

easy

A. git log --short

B. git log --oneline

C. git show --summary

D. git status --oneline

Solution

1. Step 1: Identify the correct flag for short commit view

   The --oneline option with git log shows each commit in a single line summary.

2. Step 2: Verify other options are incorrect

   git log --short is invalid, git show --summary shows details of one commit, and git status --oneline is invalid syntax.

3. Final Answer:

   git log --oneline -> Option B

4. Quick Check:

   Short commit list = git log --oneline [OK]

Hint: Use --oneline with git log for brief commit list [OK]

Common Mistakes:

• Using invalid flags like --short
• Confusing git show with git log
• Trying to use git status for commit history

3. Given this command output from git log --oneline:

f3a1b2c Fix typo in README
9d8e7f6 Add new feature X
4b3c2d1 Initial commit

What is the hash of the commit that added the new feature?

medium

A. 9d8e7f6

B. f3a1b2c

C. 4b3c2d1

D. Cannot tell from this output

Solution

1. Step 1: Read the commit messages and hashes

   The commit message "Add new feature X" corresponds to the hash 9d8e7f6.

2. Step 2: Match the message to the correct hash

   Each line shows the hash first, then the message. So the hash for adding the feature is 9d8e7f6.

3. Final Answer:

   9d8e7f6 -> Option A

4. Quick Check:

   Commit message matches hash 9d8e7f6 [OK]

Hint: First word is hash, rest is message in git log --oneline [OK]

Common Mistakes:

• Picking the wrong hash for the message
• Thinking hashes are at the end
• Assuming output is incomplete

4. You ran git log --oneline but got an error: error: unknown option `--oneline'. What is the most likely cause?

medium

A. You typed the command in the wrong folder

B. You must run git fetch before using --oneline

C. You need to add git log --oneline --all to fix it

D. Your Git version is too old and does not support --oneline

Solution

1. Step 1: Understand the error message

   The error says the option --oneline is unknown, meaning Git does not recognize it.

2. Step 2: Identify the cause

   This usually happens if the Git version is old and does not support the --oneline flag.

3. Final Answer:

   Your Git version is too old and does not support --oneline -> Option D

4. Quick Check:

   Unknown option error = outdated Git version [OK]

Hint: Unknown option often means Git version is outdated [OK]

Common Mistakes:

• Assuming wrong folder causes option error
• Thinking fetch fixes option errors
• Adding unrelated flags to fix syntax

5. You want to see a quick summary of the last 3 commits in your repository, each on one line. Which command should you use?

hard

A. git log --oneline --last 3

B. git log --3 --oneline

C. git log --oneline -n 3

D. git log --limit=3 --oneline

Solution

1. Step 1: Identify the correct option to limit commits

   The -n 3 or --max-count=3 option limits the number of commits shown.

2. Step 2: Combine with --oneline for short output

   Using git log --oneline -n 3 shows the last 3 commits in one-line format.

3. Step 3: Check other options for correctness

   --3 is invalid, --last 3 and --limit=3 are not valid git log options.

4. Final Answer:

   git log --oneline -n 3 -> Option C

5. Quick Check:

   Limit commits with -n, short view with --oneline [OK]

Hint: Use -n with --oneline to limit commits shown [OK]

Common Mistakes:

• Using invalid flags like --last or --limit
• Trying --3 which is invalid
• Mixing order of options incorrectly