Integer types in Rust - Time & Space Complexity

Time Complexity: Integer types

O(n)

Understanding Time Complexity

When working with integer types in Rust, it's helpful to know how operations on them affect program speed.

We want to see how the time to run code changes as the numbers get bigger or smaller.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_numbers(numbers: &[i32]) -> i32 {
    let mut sum = 0;
    for &num in numbers {
        sum += num;
    }
    sum
}

This code adds up all the integers in a list and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each integer to the sum inside a loop.
• How many times: Once for every number in the list.

How Execution Grows With Input

As the list gets longer, the number of additions grows at the same rate.

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

Pattern observation: Doubling the list size doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to add numbers grows directly with how many numbers there are.

Common Mistake

[X] Wrong: "Adding integers is always instant, so time doesn't grow with input size."

[OK] Correct: While each addition is fast, doing many additions one after another takes more time as the list grows.

Interview Connect

Understanding how simple operations like adding integers scale helps you explain program speed clearly and confidently.

Self-Check

"What if we changed the list to a nested list of integers? How would the time complexity change?"

Practice

1. Which Rust integer type can store only positive whole numbers including zero?

easy

A. u32

B. i32

C. f32

D. bool

Solution

1. Step 1: Understand signed vs unsigned integers

   Signed integers (i32) store negative and positive numbers, unsigned (u32) store only zero and positive numbers.

2. Step 2: Identify the type that stores only positive whole numbers

   u32 is unsigned 32-bit integer, so it stores only positive whole numbers including zero.

3. Final Answer:

   u32 -> Option A

4. Quick Check:

   Unsigned integer = u32 [OK]

Hint: Unsigned integers start with 'u' and hold only positive numbers [OK]

Common Mistakes:

• Confusing signed and unsigned types
• Choosing floating-point types for whole numbers
• Thinking bool is an integer type

2. Which of the following is the correct way to declare a 16-bit signed integer variable named x with value 100 in Rust?

easy

A. let x: u16 = 100;

B. let x: i16 = 100;

C. let x i16 = 100;

D. let x: int16 = 100;

Solution

1. Step 1: Check Rust syntax for typed variable declaration

   Rust uses let variable_name: type = value; syntax.

2. Step 2: Identify the correct 16-bit signed integer type

   i16 is the 16-bit signed integer type in Rust.

3. Final Answer:

   let x: i16 = 100; -> Option B

4. Quick Check:

   Typed variable declaration with i16 = let x: i16 = 100; [OK]

Hint: Use 'let var: i16 = value;' for 16-bit signed integers [OK]

Common Mistakes:

• Using unsigned type u16 instead of signed
• Using invalid type name int16
• Incorrect syntax like missing colon

3. What will be the output of this Rust code?

let a: i8 = 127;
let b: i8 = 1;
let c = a.wrapping_add(b);
println!("{}", c);

medium

A. 128

B. 0

C. -128

D. Overflow error

Solution

1. Step 1: Understand i8 max value and wrapping_add behavior

   The max value for i8 is 127. Adding 1 causes overflow. wrapping_add wraps around instead of panicking.

2. Step 2: Calculate the wrapped result

   127 + 1 wraps to -128 in i8 range.

3. Final Answer:

   -128 -> Option C

4. Quick Check:

   Wrapping addition overflow wraps to -128 [OK]

Hint: wrapping_add wraps on overflow, not error [OK]

Common Mistakes:

• Expecting 128 which is out of i8 range
• Thinking it causes runtime panic
• Confusing wrapping_add with normal addition

4. Identify the error in this Rust code snippet:

let x: u8 = -5;

medium

A. Missing semicolon

B. Type u8 does not exist

C. Variable name invalid

D. Negative value assigned to unsigned integer

Solution

1. Step 1: Check the type and value compatibility

   u8 is unsigned 8-bit integer and cannot hold negative values.

2. Step 2: Identify the error cause

   Assigning -5 to u8 causes a type mismatch error.

3. Final Answer:

   Negative value assigned to unsigned integer -> Option D

4. Quick Check:

   Unsigned integer cannot hold negative values [OK]

Hint: Unsigned types cannot hold negative numbers [OK]

Common Mistakes:

• Ignoring negative sign allowed in unsigned types
• Thinking semicolon is missing
• Assuming variable name is invalid

5. You need to store the number of stars in the Milky Way galaxy, approximately 20,000,000,000,000,000,000 (20 quintillion). Which Rust integer type should you choose to store this number safely?

hard

A. u128

B. i64

C. u64

D. i32

Solution

1. Step 1: Understand the size limits of integer types

   u64 max is about 18 quintillion, which cannot hold 20 quintillion. i64 max is about 9 quintillion. u128 is necessary.

2. Step 2: Choose the type that safely stores 20 quintillion

   u128 can store very large positive integers up to 3.4e38, safely holding 20 quintillion.

3. Final Answer:

   u128 -> Option A

4. Quick Check:

   Use u128 for very large positive integers [OK]

Hint: Use u128 for very large positive integers beyond u64 [OK]

Common Mistakes:

• Choosing signed types unnecessarily
• Using i32 which is too small
• Assuming u64 is always enough without checking limits