First embedded program (LED blink) in Embedded C - Time & Space Complexity

Time Complexity: First embedded program (LED blink)

O(n)

Understanding Time Complexity

When we write a program to blink an LED, it runs some instructions repeatedly to turn the light on and off.

We want to know how the time the program takes changes as we change how long it blinks or how many times it blinks.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <avr/io.h>
#include <util/delay.h>

int main(void) {
    DDRB |= (1 << PB0); // Set pin as output
    while(1) {
        PORTB |= (1 << PB0);  // LED ON
        _delay_ms(500);          // Wait 500 ms
        PORTB &= ~(1 << PB0); // LED OFF
        _delay_ms(500);          // Wait 500 ms
    }
}
    

This code turns an LED on and off repeatedly with a delay in between.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The infinite while(1) loop that repeats turning the LED on and off.
• How many times: It runs forever, repeating the on-off cycle endlessly.

How Execution Grows With Input

Here, the program runs the same steps over and over without changing based on input size.

Input Size (n)	Approx. Operations
10 cycles	About 10 on-off steps
100 cycles	About 100 on-off steps
1000 cycles	About 1000 on-off steps

Pattern observation: The time grows linearly with the number of blink cycles you want.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly with how many times the LED blinks.

Common Mistake

[X] Wrong: "The program runs in constant time because it just blinks the LED."

[OK] Correct: Even though the code loops forever, the total time depends on how many blink cycles you count. More cycles mean more time.

Interview Connect

Understanding how loops affect time helps you explain how embedded programs behave over time, a key skill for real devices.

Self-Check

"What if we changed the delay from 500 ms to 1000 ms? How would the time complexity change?"

Practice

1. What is the main purpose of the first embedded program that blinks an LED?

easy

A. To read data from a sensor

B. To turn the LED on and off repeatedly

C. To send data over a network

D. To display text on a screen

Solution

1. Step 1: Understand the program's goal

   The program is designed to control an LED by switching it on and off.

2. Step 2: Identify the blinking action

   Blinking means turning the LED on, then off repeatedly to create a visible effect.

3. Final Answer:

   To turn the LED on and off repeatedly -> Option B

4. Quick Check:

   LED blinking = on/off repeatedly [OK]

Hint: Blinking means LED toggles on and off repeatedly [OK]

Common Mistakes:

• Confusing blinking with sensor reading
• Thinking it sends data over network
• Assuming it displays text

2. Which line correctly sets the pin connected to the LED as an output in embedded C?

easy

A. DDRB |= (1 << 5);

B. PORTB |= (1 << 5);

C. PINB |= (1 << 5);

D. DDRB &= ~(1 << 5);

Solution

1. Step 1: Understand DDR register usage

   DDRB controls the data direction of port B pins; setting a bit to 1 makes it output.

2. Step 2: Analyze each option

   DDRB |= (1 << 5); sets bit 5 of DDRB to 1, configuring pin 5 as output. PORTB |= (1 << 5); sets PORTB bit, which controls output level, not direction. PINB |= (1 << 5); sets PINB, which reads input pins. DDRB &= ~(1 << 5); clears bit 5 in DDRB, making it input.

3. Final Answer:

   DDRB |= (1 << 5); -> Option A

4. Quick Check:

   Set DDRB bit = output pin [OK]

Hint: Use DDRx |= (1 << pin) to set output pin [OK]

Common Mistakes:

• Using PORT register to set direction
• Using PIN register instead of DDR
• Clearing DDR bit instead of setting

3. Given the code snippet below, what will be the output behavior of the LED?

DDRB |= (1 << 5);
while(1) {
  PORTB |= (1 << 5);
  _delay_ms(500);
  PORTB &= ~(1 << 5);
  _delay_ms(500);
}

medium

A. LED stays ON permanently

B. LED blinks with 1 second ON and 1 second OFF

C. LED stays OFF permanently

D. LED blinks with 500ms ON and 500ms OFF

Solution

1. Step 1: Analyze pin direction and control

   DDRB |= (1 << 5) sets pin 5 as output. PORTB |= (1 << 5) turns LED ON. PORTB &= ~(1 << 5) turns LED OFF.

2. Step 2: Understand delay timing

   Each _delay_ms(500) pauses for 500 milliseconds, so LED is ON for 500ms, then OFF for 500ms, repeating.

3. Final Answer:

   LED blinks with 500ms ON and 500ms OFF -> Option D

4. Quick Check:

   Delay 500ms ON/OFF = blinking every 1 second [OK]

Hint: Delay 500ms twice means 1 second blink cycle [OK]

Common Mistakes:

• Confusing delay time units
• Assuming LED stays always ON or OFF
• Ignoring bitwise operations on PORTB

4. Identify the error in the following embedded C code for blinking an LED:

DDRB = (1 << 5);
while(1) {
  PORTB = (1 << 5);
  _delay_ms(500);
  PORTB = 0;
  _delay_ms(500);
}

medium

A. DDRB should use |= instead of = to avoid clearing other pins

B. PORTB should use &= ~ instead of = to turn off LED

C. _delay_ms function is missing a header file

D. The code has no errors and will blink LED correctly

Solution

1. Step 1: Check DDRB assignment

   Using DDRB = (1 << 5) overwrites all other bits, possibly affecting other pins. Using DDRB |= (1 << 5) sets only bit 5 without changing others.

2. Step 2: Verify PORTB usage

   PORTB = (1 << 5) and PORTB = 0 are valid to turn LED ON and OFF by setting and clearing all bits respectively.

3. Final Answer:

   DDRB should use |= instead of = to avoid clearing other pins -> Option A

4. Quick Check:

   Use |= to set bits without clearing others [OK]

Hint: Use |= to set bits, not = which clears others [OK]

Common Mistakes:

• Overwriting DDRB clears other pin directions
• Confusing PORTB clearing methods
• Assuming no header needed for delay

5. You want to modify the LED blink program to blink twice as fast without changing the delay function. Which change should you make?

hard

A. Change the LED pin to a different port

B. Reduce both delay calls to 250ms

C. Toggle the LED pin twice inside the same delay period

D. Increase the delay calls to 1000ms

Solution

1. Step 1: Understand blinking speed relation

   Blink speed depends on how often the LED state changes. Delays control timing between toggles.

2. Step 2: Analyze options

   Reduce both delay calls to 250ms changes delay times, but question says without changing delay function. Toggle the LED pin twice inside the same delay period toggles LED pin twice in same delay period, effectively doubling blink frequency. Change the LED pin to a different port changes port, unrelated to speed. Increase the delay calls to 1000ms increases delay, slowing blink.

3. Final Answer:

   Toggle the LED pin twice inside the same delay period -> Option C

4. Quick Check:

   More toggles per delay = faster blink [OK]

Hint: Toggle LED more often per delay to speed up blink [OK]

Common Mistakes:

• Changing delay values despite instructions
• Changing port does not affect blink speed
• Increasing delay slows blinking