History command and search in Linux CLI - Time & Space Complexity

Time Complexity: History command and search

O(n)

Understanding Time Complexity

When using the history command with search, we want to know how long it takes to find a past command as the history grows.

We ask: How does the search time change when the history list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

history | grep "search_term"

This code lists all past commands and filters them to show only those containing "search_term".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each command line in history to see if it contains the search term.
• How many times: Once for every command stored in history.

How Execution Grows With Input

As the number of commands in history grows, the search checks more lines one by one.

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

Pattern observation: The number of checks grows directly with the number of commands in history.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows in a straight line as the history list gets longer.

Common Mistake

[X] Wrong: "The search is instant no matter how big the history is."

[OK] Correct: The command checks each line one by one, so more history means more work and longer search time.

Interview Connect

Understanding how search time grows helps you explain efficiency in real tasks, showing you know how tools behave as data grows.

Self-Check

"What if we used a command that indexed history for faster search? How would the time complexity change?"

Practice

1. What does the history command do in a Linux terminal?

easy

A. Deletes all saved commands

B. Lists all previously executed commands

C. Shows current running processes

D. Clears the terminal screen

Solution

1. Step 1: Understand the purpose of history

   The history command shows a list of commands you typed before in the terminal.

2. Step 2: Compare options with command behavior

   Only Lists all previously executed commands correctly describes this behavior; others describe different commands.

3. Final Answer:

   Lists all previously executed commands -> Option B

4. Quick Check:

   history lists past commands [OK]

Hint: Remember: history shows past commands typed [OK]

Common Mistakes:

• Confusing history with clearing screen
• Thinking history deletes commands
• Mixing history with process listing

2. Which of the following is the correct syntax to rerun the last command starting with git?

easy

A. !!git

B. !$git

C. !git

D. !^git

Solution

1. Step 1: Recall syntax for rerunning commands by prefix

   Using !string reruns the last command starting with string.

2. Step 2: Analyze options

   !git reruns last command starting with 'git'. Others are invalid or incorrect syntax.

3. Final Answer:

   !git -> Option C

4. Quick Check:

   Use !string to rerun commands [OK]

Hint: Use ! plus command start to rerun quickly [OK]

Common Mistakes:

• Using !!git which is invalid
• Confusing !$ with rerun syntax
• Trying !^git which is not correct

3. Given the following history output:

  100  ls -l
  101  git status
  102  cd projects
  103  git commit -m 'fix'

What command will run if you type !git?

medium

A. git commit -m 'fix'

B. git status

C. ls -l

D. cd projects

Solution

1. Step 1: Identify last command starting with 'git'

   From history, commands 101 and 103 start with 'git'. The last one is 103: git commit -m 'fix'.

2. Step 2: Understand !git runs last matching command

   !git reruns the most recent command starting with 'git', which is command 103.

3. Final Answer:

   git commit -m 'fix' -> Option A

4. Quick Check:

   !string runs last command starting with string [OK]

Hint: !string runs last command starting with string [OK]

Common Mistakes:

• Choosing first matching command instead of last
• Confusing command numbers with commands
• Selecting unrelated commands

4. You tried to rerun a command with !cd but got an error: bash: !cd: event not found. What is the likely cause?

medium

A. The shell does not support history

B. You typed the command incorrectly

C. You need to use !! instead

D. No previous command starts with 'cd' in history

Solution

1. Step 1: Understand error meaning

   event not found means no matching command found in history for the given prefix.

2. Step 2: Analyze cause

   If no previous command starts with 'cd', !cd fails with this error.

3. Final Answer:

   No previous command starts with 'cd' in history -> Option D

4. Quick Check:

   !string fails if no matching command [OK]

Hint: Check history for matching commands before using !string [OK]

Common Mistakes:

• Assuming syntax error instead of missing history
• Thinking shell lacks history support
• Using !! instead of !string incorrectly

5. You want to find and rerun a command that contains the word backup anywhere in it, but you don't remember the exact command start. Which is the best way to do this?

hard

A. Press Ctrl + r and type 'backup' to search interactively

B. Use !backup to rerun the command

C. Run history | grep backup and then rerun manually

D. Use !! backup to rerun last backup command

Solution

1. Step 1: Understand searching commands with unknown start

   !string only matches commands starting with string, so !backup won't find commands containing 'backup' elsewhere.

2. Step 2: Identify interactive search method

   Ctrl + r lets you search history interactively for any substring, including 'backup'.

3. Final Answer:

   Press Ctrl + r and type 'backup' to search interactively -> Option A

4. Quick Check:

   Use Ctrl + r for substring history search [OK]

Hint: Use Ctrl + r to search history by any word quickly [OK]

Common Mistakes:

• Assuming !backup matches anywhere in command
• Trying !! backup which is invalid syntax
• Relying only on grep without rerun shortcut