Compound data types in Rust - Time & Space Complexity

Time Complexity: Compound data types

O(n)

Understanding Time Complexity

When working with compound data types like tuples and structs, it's important to know how the time to access or create them changes as they grow.

We want to see how the program's work grows when handling these combined pieces of data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    x: i32,
    y: i32,
}

fn create_points(n: usize) -> Vec {
    let mut points = Vec::with_capacity(n);
    for i in 0..n {
        points.push(Point { x: i as i32, y: (i * 2) as i32 });
    }
    points
}
    

This code creates a list of points, each with two numbers, and adds them one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that runs from 0 to n, creating and adding a Point each time.
• How many times: Exactly n times, once for each point.

How Execution Grows With Input

Each new point takes a small, fixed amount of work to create and add.

Input Size (n)	Approx. Operations
10	About 10 point creations and insertions
100	About 100 point creations and insertions
1000	About 1000 point creations and insertions

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

Final Time Complexity

Time Complexity: O(n)

This means the time to create the points grows in a straight line with the number of points.

Common Mistake

[X] Wrong: "Creating a compound data type like a struct takes more time as it has more fields, so it grows faster than the number of items."

[OK] Correct: Each struct creation takes a fixed small time regardless of the number of fields, so the total time depends mostly on how many structs you create, not how many fields each has.

Interview Connect

Understanding how loops over compound data types affect time helps you explain your code clearly and shows you can think about efficiency in real projects.

Self-Check

"What if we changed the code to create nested structs inside each Point? How would the time complexity change?"

Practice

1. Which of the following best describes a tuple in Rust?

easy

A. A named collection of fields with the same type.

B. A dynamically sized list of elements all of the same type.

C. A fixed-size collection of values of possibly different types grouped together.

D. A function that returns multiple values.

Solution

1. Step 1: Understand tuple characteristics

   Tuples group multiple values of different types into one fixed-size compound value.

2. Step 2: Compare with other options

   A dynamically sized list of elements all of the same type describes arrays/vecs. A named collection of fields describes structs. A function that returns multiple values is unrelated to tuples.

3. Final Answer:

   A fixed-size collection of values of possibly different types grouped together. -> Option C

4. Quick Check:

   Tuple = fixed-size, mixed types [OK]

Hint: Tuples hold fixed mixed types by position [OK]

Common Mistakes:

• Confusing tuples with arrays (dynamic size, same type)
• Thinking tuples have named fields like structs
• Assuming tuples can change size after creation

2. Which of the following is the correct syntax to define a tuple with an integer and a string in Rust?

easy

A. let my_tuple = [42, "hello"];

B. let my_tuple = (42, "hello");

C. let my_tuple = {42, "hello"};

D. let my_tuple = <42, "hello">;

Solution

1. Step 1: Recall tuple syntax

   Tuples use parentheses () with comma-separated values, e.g., (value1, value2).

2. Step 2: Check each option

   let my_tuple = (42, "hello"); uses parentheses correctly. let my_tuple = [42, "hello"]; uses square brackets (arrays). let my_tuple = {42, "hello"}; uses braces (blocks or structs). let my_tuple = <42, "hello">; uses angle brackets which are invalid here.

3. Final Answer:

   let my_tuple = (42, "hello"); -> Option B

4. Quick Check:

   Tuple syntax uses () [OK]

Hint: Tuples use parentheses () not brackets [] or braces {} [OK]

Common Mistakes:

• Using square brackets [] instead of parentheses ()
• Using braces {} which define blocks or structs
• Using angle brackets <> which are invalid here

3. What is the output of the following Rust code?

let person = ("Alice", 30);
println!("{} is {} years old", person.0, person.1);

medium

A. Alice is 30 years old

B. ("Alice", 30) is {} years old

C. person.0 is person.1 years old

D. Compilation error due to tuple access

Solution

1. Step 1: Understand tuple indexing

   Tuple elements are accessed by position using dot and index, e.g., person.0 is "Alice", person.1 is 30.

2. Step 2: Analyze the println! macro

   The placeholders {} are replaced by person.0 and person.1 values, printing "Alice is 30 years old".

3. Final Answer:

   Alice is 30 years old -> Option A

4. Quick Check:

   Tuple access person.0 and person.1 works [OK]

Hint: Access tuple elements by .0, .1, etc. [OK]

Common Mistakes:

• Trying to access tuple elements by name instead of position
• Confusing tuple with array indexing syntax
• Expecting tuple to print as a whole automatically

4. Identify the error in this Rust struct definition and fix it:

struct Point {
    x: i32,
    y i32,
}

medium

A. Trailing comma after last field is not allowed.

B. Struct fields cannot be integers.

C. Struct names must be lowercase.

D. Missing colon after y in struct field declaration.

Solution

1. Step 1: Check struct field syntax

   Each field must have a name, colon, and type. The field 'y i32' is missing a colon.

2. Step 2: Validate other options

   Fields can be integers (i32). Struct names are PascalCase by convention. Trailing commas are allowed in Rust structs.

3. Final Answer:

   Missing colon after y in struct field declaration. -> Option D

4. Quick Check:

   Field syntax requires colon between name and type [OK]

Hint: Struct fields need name: type syntax [OK]

Common Mistakes:

• Omitting colon between field name and type
• Thinking trailing commas are errors
• Using lowercase struct names (allowed but not idiomatic)

5. Given the struct and tuple below, which code correctly creates a struct instance from the tuple values?

struct Color {
    red: u8,
    green: u8,
    blue: u8,
}

let rgb = (255, 100, 50);

hard

A. let color = Color { red: rgb.0, green: rgb.1, blue: rgb.2 };

B. let color = Color(rgb.0, rgb.1, rgb.2);

C. let color = Color { 255, 100, 50 };

D. let color = (red: 255, green: 100, blue: 50);

Solution

1. Step 1: Understand struct initialization

   Structs with named fields require field names and values in braces, e.g., Color { red: val, green: val, blue: val }.

2. Step 2: Use tuple values correctly

   Tuple elements are accessed by position: rgb.0, rgb.1, rgb.2. let color = Color { red: rgb.0, green: rgb.1, blue: rgb.2 }; uses this correctly.

3. Step 3: Check incorrect options

   let color = Color(rgb.0, rgb.1, rgb.2); uses tuple struct syntax, but Color is not a tuple struct. let color = Color { 255, 100, 50 }; omits field names. let color = (red: 255, green: 100, blue: 50); is invalid syntax.

4. Final Answer:

   let color = Color { red: rgb.0, green: rgb.1, blue: rgb.2 }; -> Option A

5. Quick Check:

   Struct init needs field names with values [OK]

Hint: Use field names when creating structs from tuples [OK]

Common Mistakes:

• Trying to initialize struct without field names
• Using tuple struct syntax for normal structs
• Incorrect syntax for struct initialization