Timer prescaler and clock division in Embedded C - Time & Space Complexity

Time Complexity: Timer prescaler and clock division

O(n)

Understanding Time Complexity

When using timers in embedded C, the prescaler changes how fast the timer counts. This affects how many steps the timer takes for a given time.

We want to understand how the timer's counting speed changes as we adjust the prescaler.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Set timer prescaler
void Timer_SetPrescaler(int prescaler) {
    TIMER->PSC = prescaler;  // Prescaler register
    TIMER->CNT = 0;          // Reset counter
    TIMER->CR1 |= 1;         // Enable timer
}

// Wait for timer to reach a value
void Timer_Wait(int target) {
    while (TIMER->CNT < target) {
        // wait
    }
}
    

This code sets a prescaler to slow down the timer clock and waits until the timer counter reaches a target value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop in Timer_Wait repeatedly checks the timer counter.
• How many times: The loop runs until the timer counter reaches the target value, which depends on the target.

How Execution Grows With Input

The number of loop checks grows roughly with the target value.

Input Size (target)	Approx. Loop Checks
10	About 10
100	About 100
1000	About 1000

Pattern observation: Increasing the target increases loop checks linearly. The prescaler slows the timer clock but does not increase the number of loop iterations.

Final Time Complexity

Time Complexity: O(n)

This means the waiting time grows linearly with the target count, but the prescaler slows the timer, effectively reducing the speed of counting.

Common Mistake

[X] Wrong: "The prescaler changes the time complexity class of the timer wait loop."

[OK] Correct: The prescaler only changes the speed of counting, not how the number of steps grows with the target. The loop still grows linearly with the target value.

Interview Connect

Understanding how timer prescalers affect counting speed helps you reason about delays and timing in embedded systems, a key skill for real-world device programming.

Self-Check

"What if we changed the waiting condition to check for an interrupt flag instead of polling the counter? How would the time complexity change?"