Summarizing long articles and documents in AI for Everyone - Time & Space Complexity

Time Complexity: Summarizing long articles and documents

O(n)

Understanding Time Complexity

When summarizing long articles or documents, it is important to understand how the time needed grows as the text gets longer.

We want to know how the work increases when the input text size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function summarizeText(text) {
  const sentences = splitIntoSentences(text);
  const importantSentences = [];
  for (const sentence of sentences) {
    if (isImportant(sentence)) {
      importantSentences.push(sentence);
    }
  }
  return combineSentences(importantSentences);
}
    

This code splits a long text into sentences, checks each sentence for importance, and collects important ones to create a summary.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each sentence to check importance.
• How many times: Once for every sentence in the text.

How Execution Grows With Input

As the number of sentences grows, the time to check each one grows at the same rate.

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

Pattern observation: The work grows directly with the number of sentences; doubling sentences doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to summarize grows in a straight line with the length of the text.

Common Mistake

[X] Wrong: "Checking sentences for importance takes the same time no matter how many sentences there are."

[OK] Correct: Each sentence must be checked individually, so more sentences mean more work.

Interview Connect

Understanding how processing time grows with input size helps you explain and improve AI tasks like summarization clearly and confidently.

Self-Check

"What if the importance check itself involved looking at every word in a sentence? How would the time complexity change?"