DNF types (Disjunctive Normal Form) in PHP - Time & Space Complexity

Time Complexity: DNF types (Disjunctive Normal Form)

O(c x k)

Understanding Time Complexity

We want to understand how the time it takes to check DNF types grows as the input gets bigger.

Specifically, how does the number of checks change when we have more parts in the DNF?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function checkDNF(array $dnf, $value): bool {
    foreach ($dnf as $clause) {
        $allTrue = true;
        foreach ($clause as $condition) {
            if (!checkCondition($condition, $value)) {
                $allTrue = false;
                break;
            }
        }
        if ($allTrue) {
            return true;
        }
    }
    return false;
}

function checkCondition($condition, $value): bool {
    // Imagine some simple check here
    return $value === $condition;
}
    

This code checks if a value matches any clause in a DNF type, where each clause is a list of conditions all needing to be true.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over clauses and conditions.
• How many times: Outer loop runs once per clause, inner loop runs once per condition in that clause.

How Execution Grows With Input

As the number of clauses and conditions grows, the checks multiply.

Input Size (n)	Approx. Operations
10 clauses x 5 conditions	About 50 checks
100 clauses x 5 conditions	About 500 checks
100 clauses x 100 conditions	About 10,000 checks

Pattern observation: The total checks grow roughly by multiplying clauses and conditions.

Final Time Complexity

Time Complexity: O(c x k)

This means the time grows proportionally to the number of clauses times the number of conditions per clause.

Common Mistake

[X] Wrong: "The time grows only with the number of clauses, ignoring conditions inside."

[OK] Correct: Each clause has multiple conditions that all must be checked, so conditions multiply the work.

Interview Connect

Understanding how nested checks grow helps you explain and reason about complex type checks or logical expressions in real code.

Self-Check

"What if we short-circuit the outer loop only after checking all clauses? How would the time complexity change?"