Analyzing Conditional Statements
What you'll learn: How to determine the runtime of code containing if-else branches by identifying the dominant execution path.
The Core Idea
When your code contains if-else statements, not all paths execute on every run. To analyze runtime, you need to count operations for each possible branch, then choose the branch that matters most for your analysis.
For worst-case analysis (most common), you pick whichever branch takes the longest. For best-case, you pick the fastest branch. For average-case, you'd consider all branches weighted by probability—but worst-case is typically what we care about.
How It Works
Think of conditional statements like a fork in the road. When counting operations:
- Count operations before the conditional (always executed)
- Count operations in the
ifbranch - Count operations in the
elsebranch (if it exists) - Add the maximum of steps 2 and 3 to step 1 for worst-case
Example walkthrough:
operations = 5 // 1 operation (before conditional)
if (condition):
operations = 10 // 1 operation (if branch)
operations = 15 // 1 operation (if branch)
else:
operations = 20 // 1 operation (else branch)
operations = 25 // 1 operation (after conditional)
- Before: 1 operation
- If-branch: 2 operations
- Else-branch: 1 operation
- After: 1 operation
- Worst-case total: 1 + max(2, 1) + 1 = 4 operations
The if branch dominates because it has more operations, so we use that path for our worst-case count.
Key Takeaway: When analyzing conditionals, count each branch separately and use the branch with the most operations for worst-case runtime analysis—the dominant path determines your upper bound.