Conditionals

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

◇Overview

Frequency counting for conditional statements (like if-else structures) involves considering the condition itself and the statements within the bra...

◇Details / Theory

Frequency counting for conditional statements (like if-else structures) involves considering the condition itself and the statements within the branches.

◇Counting Rule for if-else

The general formula for an if-else statement is:

Total Count = Count(condition) + max(Count(if-block), Count(else-block))
Count(condition): The evaluation of the condition in the if statement is counted as 1. Count(if-block): This is the sum of the frequency counts of all statements inside the if block. Count(else-block): This is the sum of the frequency counts of all statements inside the else block. If there is no else block, its count is 0.

We take the maximum of the counts of the if-block and else-block because, in any single execution, only one of these blocks (or neither, if the condition is false and there's no else) will be executed.

◇Example 1: if-else

[1] if choice == "S" // Condition

[2] read(side)

[3] area = side * side

[4] else

[5] read(base)

[6] read(height)

[7] area = (base * height) / 2.0
Line [1] (condition choice == "S"): Count = 1
If-block (lines [2, 3]):
read(side): Count = 1
area = side * side: Count = 1
Total for if-block: 1 + 1 = 2
Else-block (lines [5, 6, 7]):
read(base): Count = 1
read(height): Count = 1
area = (base * height) / 2.0: Count = 1
Total for else-block: 1 + 1 + 1 = 3
Total Frequency Count:
Count(condition) + max(Count(if-block), Count(else-block))
1 + max(2, 3)
1 + 3 = 4

◇Example 2: if without else

[1] if (a % 10 != 5) // Condition

[2] b = a + 5 - a % 10

* **Line [1] (condition `a % 10 != 5`):** Count = 1

* **If-block (line [2]):**
    * `b = a + 5 - a % 10`: Count = 1
    * **Total for if-block:** 1

* **Else-block:** Not present, so Count(else-block) = 0

* **Total Frequency Count:**
    * Count(condition) + max(Count(if-block), Count(else-block))
    * 1 + max(1, 0)
    * 1 + 1 = **2**

For `else if` structures, they can be thought of as nested `if-else` statements.

[1] if x < 1

[2] y = 10

[3] else if x < 2

[4] y = 20

[5] z = 30

[6] else

[7] for i = 1 to x

[8] print(i)

This is equivalent to:

[1] if x < 1 // Count = 1

[2] y = 10 // Count = 1 (if-block1)

[3] else // This 'else' contains another if-else

[3a] if x < 2 // Count = 1 (condition2)

[4] y = 20 // Count = 1

[5] z = 30 // Count = 1 (if-block2, total 2)

[6] else // Else for the inner if

[7] for i = 1 to x // Count = x + 1 (see ◇Loops)

[8] print(i) // Count = x (see ◇Loops)

// (else-block2, total (x+1)+x = 2x+1)
Count for outer if (line 1): 1 Count for y=10 (line 2): 1 Count for inner if (line 3a): 1 Count for y=20 and z=30 (lines 4, 5): 1 + 1 = 2 Count for the loop (lines 7, 8): $(x+1) + x = 2x+1$ Total for the else if part (lines 3-8): $1 + \text{max}(2, 2x+1)$ Overall Total: $1 + \text{max}(1, 1 + \text{max}(2, 2x+1))$

Assuming $x \ge 2$ for the else branch of the else if to be dominant:
Total = $1 + (1 + (2x+1)) = 1 + 1 + 2x + 1 = 2x + 3$.
This matches the example from "02.2 - Frequency Count Part 2.pdf" page 2.
The count for the else on line [6] itself is not explicitly 1; rather, the structure dictates which path's statements are counted. The conditions themselves (line [1] and line [3]) are each 1.

◇Complexity

◇Common Pitfalls

Forgetting to count the condition check itself as 1 operation before counting the branch body Adding if-block and else-block counts instead of taking the maximum — worst-case analysis uses max(if-block, else-block) Miscounting else-if chains — each condition check adds 1, and you still take the max across all branches Overlooking nested conditionals inside loops — the conditional's max count gets multiplied by the loop's iteration count Incorrectly assuming both branches execute — only one branch runs per invocation; frequency count reflects the costliest path

◇Summary

TL;DR — For if-else frequency counting: count the condition as 1 operation, then take the maximum of the if-block and else-block counts. For else-if chains, count each condition check and take the max across all branches. Nested conditionals inside loops multiply accordingly.

◇Links

Related: - ◇Loops Source / Reference:

◇References & Navigation

• Previous Topic: ◇Big-Theta Notation
• Next Topic: ◇Context & Relationships
• Related Notes: ◇Loops, ◇Declarations