Default method implementations in Rust - Time & Space Complexity

Time Complexity: Default method implementations

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with default method implementations changes as the input grows.

Specifically, how does calling a default method affect the total work done when used in a loop?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

trait Greeter {
    fn greet(&self) {
        println!("Hello!");
    }
}

struct Person;

impl Greeter for Person {}

fn greet_many(times: usize) {
    let p = Person;
    for _ in 0..times {
        p.greet();
    }
}
    

This code defines a trait with a default greet method and calls it many times in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the default greet method inside a loop.
• How many times: The greet method is called once for each loop iteration, so times times.

How Execution Grows With Input

Each time we increase the input times, the greet method runs that many times.

Input Size (times)	Approx. Operations
10	10 greet calls
100	100 greet calls
1000	1000 greet calls

Pattern observation: The total work grows directly with the number of times we call the method.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of method calls.

Common Mistake

[X] Wrong: "Since the method is default and simple, calling it many times is almost free and does not add up."

[OK] Correct: Even simple methods take time each call, so calling them repeatedly adds up linearly with the number of calls.

Interview Connect

Understanding how default methods behave in loops helps you explain performance clearly and shows you can reason about code efficiency beyond just syntax.

Self-Check

"What if the greet method called another method inside that also loops over the input? How would the time complexity change?"

Practice

1. What is the main purpose of default method implementations in Rust traits?

easy

A. To automatically generate structs from traits

B. To force all types to implement the method themselves

C. To prevent any method from being used outside the trait

D. To provide reusable behavior that types can use or override

Solution

1. Step 1: Understand trait default methods

   Default methods in traits provide a common implementation that types can use without writing their own code.

2. Step 2: Compare with other options

   Options A, B, and C describe behaviors that are not true for default methods in Rust traits.

3. Final Answer:

   To provide reusable behavior that types can use or override -> Option D

4. Quick Check:

   Default methods = reusable behavior [OK]

Hint: Default methods give ready code to reuse or replace [OK]

Common Mistakes:

• Thinking default methods force implementation
• Confusing traits with structs
• Believing default methods hide methods

2. Which of the following is the correct syntax to define a default method in a Rust trait?

easy

A. fn greet() { println!("Hello"); }

B. fn greet();

C. fn greet() -> { println!("Hello"); }

D. fn greet() => println!("Hello");

Solution

1. Step 1: Recall Rust trait method syntax

   Default methods in traits have a body with curly braces, like fn greet() { ... }.

2. Step 2: Check each option

   fn greet() { println!("Hello"); } uses correct syntax with braces. fn greet(); is a method signature without body (no default). Options A and D have invalid syntax.

3. Final Answer:

   fn greet() { println!("Hello"); } -> Option A

4. Quick Check:

   Default method = fn name() { body } [OK]

Hint: Default methods always have braces with code inside [OK]

Common Mistakes:

• Omitting braces for default methods
• Using arrow syntax instead of braces
• Writing only method signatures without body

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

trait Speak {
    fn say(&self) {
        println!("Default speaking");
    }
}

struct Dog;

impl Speak for Dog {}

fn main() {
    let d = Dog;
    d.say();
}

medium

A. Dog says woof

B. Compilation error: method say not implemented

C. Default speaking

D. No output

Solution

1. Step 1: Analyze trait and struct implementation

   The trait Speak has a default method say that prints "Default speaking". Dog implements Speak but does not override say.

2. Step 2: Determine method called

   Since Dog does not override say, calling d.say() uses the default method from the trait.

3. Final Answer:

   Default speaking -> Option C

4. Quick Check:

   Default method runs if not overridden [OK]

Hint: If no override, default method runs [OK]

Common Mistakes:

• Expecting an error for missing method
• Assuming default method is not used
• Confusing struct behavior with trait methods

4. Identify the error in this Rust code using default method implementations:

trait Talk {
    fn talk(&self) {
        println!("Talking");
    }
}

struct Cat;

impl Talk for Cat {
    fn talk(&self);
}

fn main() {
    let c = Cat;
    c.talk();
}

medium

A. Trait Talk must not have default methods

B. Missing method body in impl causes compilation error

C. Struct Cat cannot implement Talk

D. No error, code runs fine

Solution

1. Step 1: Check impl block for talk method

   The impl for Cat declares fn talk(&self); without a body, which is invalid syntax in Rust.

2. Step 2: Understand default method usage

   Since Talk trait has a default talk method, Cat can omit implementing it or provide a full method body. Declaring without body causes error.

3. Final Answer:

   Missing method body in impl causes compilation error -> Option B

4. Quick Check:

   Impl methods need bodies unless default used [OK]

Hint: Impl methods must have bodies or be omitted [OK]

Common Mistakes:

• Declaring method without body in impl
• Thinking default method forces impl
• Ignoring compiler error messages

5. Given this trait and structs, how can you override the default method only for Cat while Dog uses the default?

trait Animal {
    fn sound(&self) {
        println!("Some sound");
    }
}

struct Dog;
struct Cat;

impl Animal for Dog {}
impl Animal for Cat {
    // What goes here?
}

fn main() {
    let dog = Dog;
    dog.sound();
    let cat = Cat;
    cat.sound();
}

hard

A. fn sound(&self) { println!("Meow"); }

B. fn sound(&self);

C. fn sound() { println!("Meow"); }

D. fn sound(&self) -> String { "Meow".to_string() }

Solution

1. Step 1: Understand overriding default methods

   To override a default method, provide a method with the same signature and a body in the impl block.

2. Step 2: Check options for correct override syntax

   fn sound(&self) { println!("Meow"); } correctly defines fn sound(&self) with a body printing "Meow". fn sound(&self); lacks body, causing error. fn sound() { println!("Meow"); } misses &self parameter. fn sound(&self) -> String { "Meow".to_string() } changes return type, incompatible with trait.

3. Final Answer:

   fn sound(&self) { println!("Meow"); } -> Option A

4. Quick Check:

   Override = same signature + method body [OK]

Hint: Override with same signature and method body [OK]

Common Mistakes:

• Omitting &self parameter
• Declaring method without body
• Changing return type in override