gzip and gunzip in Linux CLI - Time & Space Complexity

Time Complexity: gzip and gunzip

O(n)

Understanding Time Complexity

When using gzip and gunzip, it's important to understand how the time to compress or decompress files changes as file size grows.

We want to know how the work done by these commands grows when the input file gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following commands.

gzip largefile.txt
# Compresses the file largefile.txt into largefile.txt.gz

gunzip largefile.txt.gz
# Decompresses the file back to largefile.txt

These commands compress and decompress a file using gzip and gunzip.

Identify Repeating Operations

Both gzip and gunzip process the file data in chunks, reading and writing repeatedly.

• Primary operation: Reading and processing each byte of the file.
• How many times: Once for each byte in the file, sequentially.

How Execution Grows With Input

As the file size grows, the time to compress or decompress grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10 KB	10,240 operations
100 KB	102,400 operations
1 MB (1024 KB)	1,048,576 operations

Pattern observation: Doubling the file size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to compress or decompress grows linearly with the file size.

Common Mistake

[X] Wrong: "gzip compresses files instantly no matter the size."

[OK] Correct: Compression takes time proportional to file size because every byte must be processed.

Interview Connect

Understanding how compression tools scale with file size helps you reason about performance in real tasks, showing you can think about efficiency beyond just writing commands.

Self-Check

"What if gzip used multi-threading to compress parts of the file in parallel? How would the time complexity change?"

Practice

1. What does the gzip command do in Linux?

easy

A. Lists files in a directory

B. Deletes a file permanently

C. Compresses a file and replaces the original with a .gz file

D. Creates a backup copy of a file

Solution

1. Step 1: Understand gzip purpose

   The gzip command compresses files to save disk space.

2. Step 2: Effect on original file

   It replaces the original file with a compressed file ending in .gz.

3. Final Answer:

   Compresses a file and replaces the original with a .gz file -> Option C

4. Quick Check:

   gzip compresses files = D [OK]

Hint: gzip compresses and replaces original file by default [OK]

Common Mistakes:

• Thinking gzip deletes files without compression
• Confusing gzip with backup commands
• Assuming gzip lists files

2. Which of the following is the correct syntax to compress a file named data.txt but keep the original file?

easy

A. gzip data.txt

B. gzip -d data.txt

C. gunzip -k data.txt

D. gzip -k data.txt

Solution

1. Step 1: Identify option to keep original

   The -k option tells gzip to keep the original file after compression.

2. Step 2: Match correct command

   gzip -k data.txt compresses and keeps the original file.

3. Final Answer:

   gzip -k data.txt -> Option D

4. Quick Check:

   Use -k to keep original file [OK]

Hint: Use -k with gzip to keep original file [OK]

Common Mistakes:

• Using gunzip instead of gzip for compression
• Using -d which is for decompression
• Not using -k and losing original file

3. What will be the output of the following commands?

gzip -k report.txt
gunzip report.txt.gz

medium

A. Only report.txt exists after commands

B. Both report.txt and report.txt.gz exist after commands

C. Original report.txt deleted, only report.txt.gz remains

D. Error because gunzip cannot decompress .gz files

Solution

1. Step 1: Analyze gzip -k report.txt

   This compresses report.txt to report.txt.gz and keeps the original report.txt file.

2. Step 2: Analyze gunzip report.txt.gz

   This decompresses report.txt.gz back to report.txt and deletes the .gz file.

3. Final Answer:

   Only report.txt exists after commands -> Option A

4. Quick Check:

   gzip -k keeps original, gunzip restores and removes .gz [OK]

Hint: gunzip removes .gz file after decompression [OK]

Common Mistakes:

• Assuming gzip deletes original with -k option
• Thinking gunzip keeps .gz file after decompression
• Confusing gzip and gunzip roles

4. You run gunzip file.txt but get an error saying "not in gzip format." What is the likely problem?

medium

A. gunzip command is misspelled

B. file.txt is not a compressed .gz file

C. file.txt is already decompressed

D. You need to use gzip instead of gunzip

Solution

1. Step 1: Understand gunzip input requirement

   gunzip expects a file compressed with gzip, usually ending with .gz.

2. Step 2: Analyze error message

   "not in gzip format" means the file is not compressed or not a .gz file.

3. Final Answer:

   file.txt is not a compressed .gz file -> Option B

4. Quick Check:

   gunzip needs .gz files [OK]

Hint: gunzip only works on gzip-compressed (.gz) files [OK]

Common Mistakes:

• Trying to decompress uncompressed files
• Confusing gzip and gunzip commands
• Ignoring file extensions

5. You have multiple log files: log1.txt, log2.txt, and log3.txt. You want to compress all of them but keep the original files. Which command will do this correctly?

hard

A. gzip -k log*.txt

B. gzip log*.txt

C. gunzip -k log*.txt

D. gzip -d log*.txt

Solution

1. Step 1: Identify command to compress multiple files

   gzip compresses files; log*.txt matches all log files.

2. Step 2: Ensure original files are kept

   The -k option keeps original files after compression.

3. Final Answer:

   gzip -k log*.txt -> Option A

4. Quick Check:

   gzip -k compresses and keeps originals [OK]

Hint: Use gzip -k with wildcard to keep originals [OK]

Common Mistakes:

• Using gunzip instead of gzip for compression
• Not using -k and losing original files
• Using -d which decompresses files