head and tail in Linux CLI - Time & Space Complexity

Time Complexity: head and tail

O(1) for head, O(k) for tail where k is number of lines requested

Understanding Time Complexity

When using head and tail commands, it's helpful to know how their execution time changes as the input file grows.

We want to understand how the number of lines in a file affects how long these commands take to run.

Scenario Under Consideration

Analyze the time complexity of the following commands.

head -n 10 largefile.txt
tail -n 10 largefile.txt

These commands print the first or last 10 lines of a file named largefile.txt.

Identify Repeating Operations

Look at what the commands do repeatedly.

• Primary operation: Reading lines from the file.
• How many times: For head, it reads only the first 10 lines. For tail, it seeks to the end of the file and reads backwards only the necessary amount to find the last 10 lines.

How Execution Grows With Input

As the file gets bigger, how does the work change?

Input Size (lines)	Approx. Operations for head	Approx. Operations for tail
10	Reads 10 lines	Reads 10 lines
100	Reads 10 lines	Reads ~10 lines from end
1000	Reads 10 lines	Reads ~10 lines from end

Pattern observation: Both head and tail perform a fixed amount of work regardless of file size.

Final Time Complexity

Time Complexity: O(1) for head and O(k) for tail, where k is the number of lines requested.

This means head takes constant time, and tail takes time proportional to the number of lines requested, which is usually small and treated as constant.

Common Mistake

[X] Wrong: "tail reads through the whole file to find the last lines, making it O(n)."

[OK] Correct: In modern implementations (like GNU tail on Linux), tail seeks to the end of the file and reads backwards only enough data to identify and output the last 10 lines, making it also O(k), which is effectively constant for small k.

Interview Connect

Understanding how simple commands like head and tail behave with large files shows you can think about efficiency in everyday tasks, a skill valuable in many scripting and automation roles.

Self-Check

What if we used tail -n 10 on a file stored on a slow network drive? How might that affect the time complexity or perceived speed?

Practice

1. What does the head command do by default when run on a text file?

easy

A. Counts the number of lines in the file

B. Shows the last 10 lines of the file

C. Deletes the first 10 lines of the file

D. Shows the first 10 lines of the file

Solution

1. Step 1: Understand the default behavior of head

   The head command shows the start of a file, by default 10 lines.

2. Step 2: Compare with other options

   tail shows the end, but head shows the beginning lines.

3. Final Answer:

   Shows the first 10 lines of the file -> Option D

4. Quick Check:

   head = first 10 lines [OK]

Hint: Remember: head = start, tail = end of file [OK]

Common Mistakes:

• Confusing head with tail
• Thinking head deletes lines
• Assuming head counts lines

2. Which of the following is the correct syntax to display the last 5 lines of a file named log.txt?

easy

A. tail -n 5 log.txt

B. head -n 5 log.txt

C. tail 5 log.txt

D. head 5 log.txt

Solution

1. Step 1: Identify the command to show last lines

   tail shows the end of a file, so it is used to show last lines.

2. Step 2: Use correct syntax with -n option

   The option -n 5 specifies to show 5 lines. So tail -n 5 log.txt is correct.

3. Final Answer:

   tail -n 5 log.txt -> Option A

4. Quick Check:

   tail -n 5 shows last 5 lines [OK]

Hint: Use -n with tail to specify number of lines [OK]

Common Mistakes:

• Using head instead of tail
• Omitting -n option
• Using tail without -n for line count

3. Given a file data.txt with 20 lines, what will be the output of head -n 3 data.txt | tail -n 2?

medium

A. Lines 2 and 3 of data.txt

B. Lines 1 and 2 of data.txt

C. Lines 18 and 19 of data.txt

D. Lines 3 and 4 of data.txt

Solution

1. Step 1: Understand head -n 3 data.txt

   This command outputs the first 3 lines: lines 1, 2, and 3.

2. Step 2: Apply tail -n 2 on the output

   tail -n 2 takes the last 2 lines of the previous output, so lines 2 and 3.

3. Final Answer:

   Lines 2 and 3 of data.txt -> Option A

4. Quick Check:

   head 3 then tail 2 = lines 2 & 3 [OK]

Hint: Pipe head then tail to slice lines from start [OK]

Common Mistakes:

• Assuming tail works on whole file, not head output
• Confusing line numbers
• Thinking tail -n 2 shows first 2 lines

4. You run head -n 5 file.txt but get an error: head: invalid option -- 'n'. What is the likely cause?

medium

A. The file file.txt does not exist

B. The head command version does not support -n

C. You need to use --lines=5 instead of -n 5

D. You must run the command as root

Solution

1. Step 1: Analyze the error message

   The error says invalid option -- 'n', meaning -n is not recognized.

2. Step 2: Understand command version differences

   Some older or non-GNU versions of head do not support -n and require different syntax.

3. Final Answer:

   The head command version does not support -n -> Option B

4. Quick Check:

   Invalid option error means unsupported flag [OK]

Hint: Check command version if options cause errors [OK]

Common Mistakes:

• Assuming file missing causes option error
• Trying to run as root unnecessarily
• Using wrong syntax without checking version

5. You want to monitor the last 15 lines of a growing log file app.log in real-time but only want to see the newest lines as they appear. Which command combination is best?

hard

A. head -n 15 app.log

B. tail -n 15 app.log

C. tail -n 15 -f app.log

D. head -n 15 -f app.log

Solution

1. Step 1: Understand the need to see last lines and follow updates

   You want the last 15 lines and to watch new lines as they are added.

2. Step 2: Use tail with -n 15 and -f

   tail -n 15 -f app.log shows last 15 lines and follows file changes live.

3. Final Answer:

   tail -n 15 -f app.log -> Option C

4. Quick Check:

   tail -n 15 -f = last 15 lines + live updates [OK]

Hint: Use tail -f to follow file changes live [OK]

Common Mistakes:

• Using head which shows start, not end
• Omitting -f to follow updates
• Using head -f which is invalid