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

Analyzing Simple Loops

Counting operations in single loops and deriving runtime formulas for linear iterations.

Analyzing Simple Loops

What you'll learn: How to count operations inside a single loop and express the total runtime as a formula based on input size.


The Core Idea

When a loop runs, it repeats a block of operations multiple times. To analyze its runtime, you count how many operations happen in one iteration, then multiply by the number of iterations.

For a simple loop that runs n times (where n is your input size), if each iteration performs c constant operations, the total operation count is:

Total operations = c × n

This gives you a runtime formula that describes how the loop's cost grows with input size.


Walking Through an Example

Imagine a loop that prints each element of an array:

for i from 0 to n-1:
    print array[i]

Step 1: Count operations per iteration:

  • Access array[i]: 1 operation
  • Print: 1 operation
  • Loop overhead (increment, compare): ~2 operations

Total per iteration: ~4 operations

Step 2: Count iterations:

  • The loop runs exactly n times (once per array element)

Step 3: Multiply:

  • Total operations = 4 × n

The runtime grows linearly with n. Double the array size, double the operations.


Why This Matters

This formula lets you predict performance. An array of 1,000 elements? Expect ~4,000 operations. This systematic counting is the foundation of understanding how efficient your code is.

Key Takeaway: To analyze a simple loop, count the operations per iteration, multiply by the number of iterations, and derive a runtime formula in terms of input size n.