Why loops are needed in C - Performance Analysis

Time Complexity: Why loops are needed

O(n)

Understanding Time Complexity

Loops help us repeat actions many times without writing the same code again and again.

We want to see how the time to run code changes when we repeat tasks using loops.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

int main() {
    int sum = 0;
    for (int i = 0; i < 5; i++) {
        sum += i;
    }
    printf("Sum: %d\n", sum);
    return 0;
}
    

This code adds numbers from 0 to 4 and prints the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that adds numbers.
• How many times: It runs 5 times, once for each number from 0 to 4.

How Execution Grows With Input

Imagine if we change the loop to run more times, like 10, 100, or 1000.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of steps grows directly with how many times the loop runs.

Final Time Complexity

Time Complexity: O(n)

This means if you double the number of times the loop runs, the time to finish roughly doubles too.

Common Mistake

[X] Wrong: "Loops always take the same time no matter how many times they run."

[OK] Correct: The time depends on how many times the loop repeats; more repeats mean more time.

Interview Connect

Understanding loops and how they affect time helps you explain how programs handle repeated tasks efficiently.

Self-Check

"What if we changed the loop to run from 0 to n*n instead of 0 to n? How would the time complexity change?"