Why you must fact-check AI responses in AI for Everyone - Performance Analysis

Time Complexity: Why you must fact-check AI responses

O(n)

Understanding Time Complexity

When using AI to get answers, it is important to understand how the time it takes to check facts grows as the amount of information increases.

We want to know how much effort is needed to verify AI responses as they get longer or more complex.

Scenario Under Consideration

Analyze the time complexity of the following fact-checking process.

function factCheck(aiResponse) {
  for (const statement of aiResponse.statements) {
    if (!verify(statement)) {
      return false;
    }
  }
  return true;
}

function verify(statement) {
  // Check statement against trusted sources
  // Returns true if verified, false otherwise
}
    

This code checks each statement in an AI response one by one to see if it is true by comparing it to trusted sources.

Identify Repeating Operations

• Primary operation: Looping through each statement in the AI response.
• How many times: Once for every statement in the response.

How Execution Grows With Input

As the number of statements grows, the time to check all of them grows in a similar way.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to fact-check grows in a straight line with the number of statements to verify.

Common Mistake

[X] Wrong: "Fact-checking AI responses is instant no matter how long the response is."

[OK] Correct: Each statement needs to be checked, so longer responses take more time to verify.

Interview Connect

Understanding how time grows with input size helps you explain why verifying AI answers takes effort and how to manage it efficiently.

Self-Check

"What if the verify function itself checks multiple sources for each statement? How would that affect the time complexity?"