Course contentsShow
← Computer Science
Lesson 277 of 2,8727. Introduction to Complexity AnalysisFree lesson

Analyzing Conditional Statements

Determining runtime when code has if-else branches and choosing the dominant path.

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:

  1. Count operations before the conditional (always executed)
  2. Count operations in the if branch
  3. Count operations in the else branch (if it exists)
  4. 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.