Time Complexity: History command and search
O(n)
0
0
History command and search in Linux CLI - Time & Space Complexity
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?"