Type inference in Rust - Time & Space Complexity

Time Complexity: Type inference

O(n)

Understanding Time Complexity

When Rust figures out the type of a variable automatically, it does some work behind the scenes.

We want to see how the time it takes to guess types grows as the code gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

let values = vec![1, 2, 3, 4, 5];
let result = sum_numbers(&values);

This code sums a list of numbers. Rust infers the types of variables and function return automatically.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number in the list to add it.
• How many times: Once for each number in the input list.

How Execution Grows With Input

As the list gets longer, Rust checks each number's type once, then sums them all.

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

Pattern observation: The work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to infer types and sum grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Type inference happens instantly no matter how big the input is."

[OK] Correct: Rust must check each element's type in the list, so more items mean more work.

Interview Connect

Understanding how type inference scales helps you explain how Rust manages code efficiently behind the scenes.

Self-Check

"What if the function used nested loops over two lists? How would the time complexity change?"

Practice

1. What does Rust's type inference do when you write let x = 5; without specifying a type?

easy

A. Rust treats x as a string by default.

B. Rust throws a syntax error because the type is missing.

C. Rust requires you to write the type explicitly for all variables.

D. Rust guesses the type of x as i32 based on the value 5.

Solution

1. Step 1: Understand Rust's default integer type

   Rust uses i32 as the default integer type when no type is specified.

2. Step 2: Apply type inference to let x = 5;

   Since 5 is an integer literal, Rust infers x to be i32 automatically.

3. Final Answer:

   Rust guesses the type of x as i32 based on the value 5. -> Option D

4. Quick Check:

   Type inference = i32 for integer literals [OK]

Hint: Integer literals default to i32 if no type given [OK]

Common Mistakes:

• Thinking Rust requires explicit types always
• Assuming default type is string
• Believing missing types cause syntax errors

2. Which of the following is the correct syntax to let Rust infer the type of a floating-point number?

easy

A. let num = "3.14";

B. let num: f64 = 3.14;

C. let num = 3.14;

D. let num = 3,14;

Solution

1. Step 1: Identify valid floating-point syntax

   In Rust, floating-point literals use a dot (.) as decimal separator, so 3.14 is valid.

2. Step 2: Check type inference usage

   Writing let num = 3.14; lets Rust infer f64 type automatically.

3. Final Answer:

   let num = 3.14; -> Option C

4. Quick Check:

   Floating-point literals infer f64 by default [OK]

Hint: Use dot for decimals; omit type to infer f64 [OK]

Common Mistakes:

• Using comma instead of dot for decimals
• Confusing string literals with numbers
• Unnecessarily specifying type when inference works

3. What is the output of this Rust code?

let x = 10;
let y = 20.5;
let z = x as f64 + y;
println!("{}", z);

medium

A. 30.5

B. 30

C. Compilation error due to type mismatch

D. 10.20.5

Solution

1. Step 1: Understand type casting

   Variable x is i32, y is f64. Casting x as f64 converts it to floating-point.

2. Step 2: Calculate the sum

   After casting, 10.0 + 20.5 = 30.5. The println! prints this value.

3. Final Answer:

   30.5 -> Option A

4. Quick Check:

   Cast int to float, then add = 30.5 [OK]

Hint: Cast integers to float before adding floats [OK]

Common Mistakes:

• Expecting integer addition without cast
• Assuming implicit cast without as
• Confusing output format with concatenation

4. Identify the error in this Rust code snippet:

let a = 5;
let b = 2.0;
let c = a + b;

medium

A. Cannot add integer and floating-point without casting.

B. Variable a is not initialized.

C. Missing semicolon after let b = 2.0.

D. Rust does not support addition operator.

Solution

1. Step 1: Check variable types

   a is i32 (integer), b is f64 (floating-point).

2. Step 2: Understand addition rules in Rust

   Rust does not allow adding different numeric types directly; explicit casting is needed.

3. Final Answer:

   Cannot add integer and floating-point without casting. -> Option A

4. Quick Check:

   Mixed-type addition requires cast [OK]

Hint: Add only same types or cast explicitly [OK]

Common Mistakes:

• Ignoring type mismatch errors
• Assuming implicit conversion between int and float
• Overlooking Rust's strict type rules

5. Given this Rust code, what is the type of result?

let values = vec![1, 2, 3];
let result: Vec<f64> = values.iter().map(|&x| x as f64 * 1.5).collect();

hard

A. Vec<i32>

B. Vec<f64>

C. Vec<&i32>

D. Compilation error due to missing type annotation

Solution

1. Step 1: Analyze the iterator and map closure

   values.iter() produces references &i32. The closure |&x| x as f64 * 1.5 dereferences and casts x to f64, then multiplies.

2. Step 2: Collect into specified type

   The collect() call collects results into Vec<f64> as explicitly annotated.

3. Final Answer:

   Vec<f64> -> Option B

4. Quick Check:

   Mapping with cast and collecting matches annotated type [OK]

Hint: Check closure cast and collect type annotation [OK]

Common Mistakes:

• Confusing iterator item types with collected vector type
• Missing dereference in closure causing type errors
• Assuming collect infers wrong type without annotation