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?"