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?"

Practice

1.

What does a Disjunctive Normal Form (DNF) type represent in PHP?

easy

A. A type that disables type checking

B. A type that combines OR (union) and AND (intersection) conditions

C. A type that restricts variables to integers only

D. A type that only allows a single data type

Solution

1. Step 1: Understand DNF type concept

   DNF types combine multiple conditions using OR (union) and AND (intersection) to specify allowed types.

2. Step 2: Compare options with definition

   Only the type that combines OR (union) and AND (intersection) conditions correctly describes this combination of OR and AND conditions in PHP types.

3. Final Answer:

   A type that combines OR (union) and AND (intersection) conditions -> Option B

4. Quick Check:

   DNF types = OR + AND conditions [OK]

Hint: DNF means combining OR and AND in types [OK]

Common Mistakes:

• Thinking DNF only means union types
• Confusing DNF with simple single types
• Assuming DNF disables type checks

2.

Which of the following is the correct PHP syntax for a DNF type combining union and intersection?

function example( /* type here */ $param) {}

easy

A. int&float&Serializable

B. int&float|Serializable

C. int|float|Serializable

D. int|float&Serializable

Solution

1. Step 1: Recall PHP DNF syntax rules

   PHP uses | for union (OR) and & for intersection (AND). Intersection has higher precedence, so int|float&Serializable means int OR (float AND Serializable).

2. Step 2: Analyze each option

   int|float&Serializable correctly uses union and intersection combined. int&float|Serializable misplaces operators, C uses only union, D uses only intersection.

3. Final Answer:

   int|float&Serializable -> Option D

4. Quick Check:

   Union (|) and intersection (&) combined correctly = int|float&Serializable [OK]

Hint: Use | for OR, & for AND in PHP types [OK]

Common Mistakes:

• Mixing order of | and & operators
• Using only unions or only intersections
• Writing invalid syntax like &| or |&

3.

What is the output of this PHP code snippet?

interface A {} 
interface B {} 
class C implements A, B {} 
function test(A|B&object $param): string { 
  return $param instanceof B ? 'Yes' : 'No'; 
} 
$obj = new C(); 
echo test($obj);

medium

A. Fatal error

B. No

C. Yes

D. Empty output

Solution

1. Step 1: Understand the type declaration

   The parameter type is A OR (B AND object). Class C implements both A and B, so it matches the type.

2. Step 2: Evaluate the instanceof check

   $obj is instance of B, so the ternary returns 'Yes'.

3. Final Answer:

   Yes -> Option C

4. Quick Check:

   Object matches B, so output is 'Yes' [OK]

Hint: Check instanceof for intersection parts in DNF types [OK]

Common Mistakes:

• Assuming type mismatch causes error
• Ignoring intersection precedence
• Thinking output is 'No' without checking instanceof

4.

Identify the error in this PHP function using DNF types:

function checkType(int|float&Countable $value) { 
  return is_countable($value); 
}

medium

A. Invalid use of & with float, which is not an object

B. Missing return type declaration

C. is_countable() cannot be used here

D. int and float cannot be unioned

Solution

1. Step 1: Analyze intersection with primitive types

   float is a primitive type and cannot be combined with & Countable (an interface) because & requires object types.

2. Step 2: Confirm error cause

   Using & between float and Countable causes a type error since float is not an object.

3. Final Answer:

   Invalid use of & with float, which is not an object -> Option A

4. Quick Check:

   Intersection requires objects, float is primitive [OK]

Hint: Intersection (&) only works with object types [OK]

Common Mistakes:

• Thinking primitives can be intersected with interfaces
• Ignoring PHP type system rules
• Assuming is_countable() causes error

5.

Given these interfaces and classes:

interface X {} 
interface Y {} 
class A implements X {} 
class B implements Y {} 
class C implements X, Y {}

Which DNF type correctly accepts objects that implement either X alone, or both X and Y together?

hard

A. X|(X&Y)

B. X&Y|Y

C. X|Y

D. (X|Y)&Y

Solution

1. Step 1: Understand the requirement

   Accept objects that implement X alone OR both X and Y together.

2. Step 2: Translate to DNF

   This means either X alone OR (X AND Y). X|(X&Y) expresses this as X|(X&Y).

3. Step 3: Check other options

   X&Y|Y includes Y alone, which is incorrect. X|Y accepts X or Y alone, too broad. (X|Y)&Y includes Y alone, which is incorrect.

4. Final Answer:

   X|(X&Y) -> Option A

5. Quick Check:

   DNF matches X alone or X and Y together = X|(X&Y) [OK]

Hint: Use union of X and intersection X&Y for this case [OK]

Common Mistakes:

• Choosing simple union X|Y which is too broad
• Misplacing parentheses changing logic
• Confusing intersection and union precedence