Integer types and their ranges in C Sharp (C#) - Time & Space Complexity

Time Complexity: Integer types and their ranges

O(n)

Understanding Time Complexity

We want to understand how the size of integer types affects operations in C#.

How does the range of integers impact the work done by the program?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int SumUpTo(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

This code sums all numbers from 1 up to n using an integer variable.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop adding numbers one by one.
• How many times: It runs exactly n times, where n is the input number.

How Execution Grows With Input

As n grows, the number of additions grows the same way.

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

Pattern observation: The work grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Using bigger integer types makes the loop run faster or slower."

[OK] Correct: The integer type size affects memory but does not change how many times the loop runs or how many additions happen.

Interview Connect

Understanding how input size affects loops is a key skill. It helps you explain how your code will behave with bigger numbers.

Self-Check

"What if we changed the loop to count down from n to 1? How would the time complexity change?"