Malware analysis basics in Cybersecurity - Time & Space Complexity

Time Complexity: Malware analysis basics

O(n)

Understanding Time Complexity

When analyzing malware, understanding how the analysis time grows with the size of the malware is important.

We want to know how the effort to analyze malware changes as the malware gets bigger or more complex.

Scenario Under Consideration

Analyze the time complexity of the following malware scanning process.

for each file in system_files:
    open file
    for each byte in file:
        check if byte matches malware signature
    close file

This code scans every file byte-by-byte to find malware signatures.

Identify Repeating Operations

Look at the loops that repeat work.

• Primary operation: Checking each byte in every file.
• How many times: For each file, it checks every byte inside it.

How Execution Grows With Input

As the number of files or their sizes grow, the scanning time grows too.

Input Size (n)	Approx. Operations
10 files, 1KB each	~10,240 byte checks
100 files, 1KB each	~102,400 byte checks
100 files, 10KB each	~1,024,000 byte checks

Pattern observation: The total work grows roughly with the total number of bytes scanned.

Final Time Complexity

Time Complexity: O(n)

This means the scanning time grows directly in proportion to the total size of all files scanned.

Common Mistake

[X] Wrong: "Scanning more files only slightly increases time because files are small."

[OK] Correct: Even small files add up, and scanning every byte means time grows with total bytes, not just file count.

Interview Connect

Understanding how malware scanning time grows helps you explain efficiency and scalability in security tools.

Self-Check

"What if the malware scanner used a hash index instead of checking every byte? How would the time complexity change?"