File globbing (wildcards *, ?, []) in Linux CLI - Time & Space Complexity

Time Complexity: File globbing (wildcards *, ?, [])

O(n)

Understanding Time Complexity

When using file globbing with wildcards, the system searches for matching files. Understanding how the time grows as the number of files increases helps us know how fast or slow this search might be.

We want to know: How does the search time change when there are more files to check?

Scenario Under Consideration

Analyze the time complexity of the following file globbing command.

ls *.txt
    

This command lists all files in the current folder that end with .txt using the wildcard *.

Identify Repeating Operations

• Primary operation: Checking each file name against the pattern.
• How many times: Once for every file in the directory.

How Execution Grows With Input

As the number of files grows, the system must check more names to find matches.

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

Pattern observation: The number of checks grows directly with the number of files.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matching files grows in a straight line as the number of files increases.

Common Mistake

[X] Wrong: "The wildcard search only looks at matching files, so time stays the same no matter how many files there are."

[OK] Correct: The system must check every file name to see if it matches the pattern, so more files mean more checks and more time.

Interview Connect

Knowing how file searches scale helps you understand system performance and write scripts that run efficiently, a useful skill in many real-world tasks.

Self-Check

"What if we used a pattern like 'file?.txt' instead of '*.txt'? How would the time complexity change?"

Practice

1. Which wildcard pattern matches all files with any extension starting with log in their name?

easy

A. log* only matches files named exactly 'log'

B. log?

C. log[0-9]

D. log*

Solution

1. Step 1: Understand the wildcard *

   The * matches zero or more characters, so log* matches any file starting with 'log' followed by anything or nothing.

2. Step 2: Compare other options

   log? matches 'log' plus exactly one character, log[0-9] matches 'log' plus one digit, and the last option is incorrect about log*.

3. Final Answer:

   log* -> Option D

4. Quick Check:

   Wildcard * matches any characters [OK]

Hint: Use * to match any number of characters [OK]

Common Mistakes:

• Confusing * with ? wildcard
• Thinking * matches only one character
• Misunderstanding [] as matching multiple characters

2. Which of the following is the correct pattern to match files named data1, data2, but not data10?

easy

A. data?

B. data*

C. data[1-9]

D. data??

Solution

1. Step 1: Understand the pattern data[1-9]

   This matches 'data' followed by exactly one digit from 1 to 9, so it matches 'data1' and 'data2' but not 'data10'.

2. Step 2: Check other patterns

   data? matches 'data' plus any one character (including letters), data* matches 'data' plus any characters (including 'data10'), and data?? matches 'data' plus exactly two characters (so it matches 'data10').

3. Final Answer:

   data[1-9] -> Option C

4. Quick Check:

   Square brackets match one character from set [OK]

Hint: Use [ ] to match one character from a range [OK]

Common Mistakes:

• Using * which matches too many files
• Using ? which matches any single character, not range
• Confusing number of characters matched

3. Given files: file1.txt, file2.txt, fileA.txt, fileB.txt, what files does the pattern file?.txt match?

medium

A. file1.txt, file2.txt

B. file1.txt, file2.txt, fileA.txt, fileB.txt

C. fileA.txt, fileB.txt

D. file.txt

Solution

1. Step 1: Understand the pattern file?.txt

   The ? matches exactly one character, so it matches any file named 'file' plus one character plus '.txt'.

2. Step 2: Check which files match

   All files with names 'file1.txt', 'file2.txt', 'fileA.txt', and 'fileB.txt' have exactly one character after 'file' before '.txt', so all match.

3. Final Answer:

   file1.txt, file2.txt, fileA.txt, fileB.txt -> Option B

4. Quick Check:

   ? matches exactly one character [OK]

Hint: Use ? to match exactly one character [OK]

Common Mistakes:

• Thinking ? matches zero or multiple characters
• Confusing ? with *
• Ignoring file extension in pattern

4. You want to list files named report1, report2, and report3 only. Which pattern is incorrect?

medium

A. report*

B. report?

C. report[1-3]

D. report[123]

Solution

1. Step 1: Analyze pattern report*

   This matches 'report' plus any characters, so it matches more than just 'report1', 'report2', and 'report3'. It includes 'report10', 'report_final', etc.

2. Step 2: Check other patterns

   report[1-3] and report[123] match exactly one character from 1,2,3 after 'report'. report? matches 'report' plus any one character, which includes 'report1', 'report2', 'report3' but also others with one character.

3. Final Answer:

   report* -> Option A

4. Quick Check:

   * matches too many files [OK]

Hint: Use [] to limit characters, * matches too many [OK]

Common Mistakes:

• Using * when exact matches needed
• Assuming ? limits to digits only
• Not realizing [] matches one character only

5. You have files: img01.png, img02.png, img10.png, img20.png. Which pattern matches only files with numbers from 01 to 09?

hard

A. img0[1-9].png

B. img[0-9][1-9].png

C. img??.png

D. img[01-09].png

Solution

1. Step 1: Understand pattern img0[1-9].png

   This matches 'img0' plus one digit from 1 to 9, then '.png'. So it matches 'img01.png' to 'img09.png'.

2. Step 2: Check other patterns

   img[0-9][1-9].png matches any two digits, including 'img10.png' and 'img20.png'. img??.png matches any two characters after 'img', so all files. img[01-09].png is invalid syntax because ranges like '01-09' are not valid inside [].

3. Final Answer:

   img0[1-9].png -> Option A

4. Quick Check:

   Use 0 then [1-9] for numbers 01-09 [OK]

Hint: Use fixed digit then range in [] for number ranges [OK]

Common Mistakes:

• Using invalid range syntax inside []
• Using ?? which matches any two characters
• Not fixing leading zero for 01-09