Nested structures in C++ - Time & Space Complexity

Time Complexity: Nested structures

O(n)

Understanding Time Complexity

When we use nested structures in code, it often means some parts repeat inside others.

We want to see how the total work grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Inner {
    int value;
};

struct Outer {
    Inner arr[5];
};

void process(Outer data[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            data[i].arr[j].value += 1;
        }
    }
}
    

This code loops through an array of Outer structures, each containing an array of Inner structures, and updates a value inside each Inner.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop updates each Inner element's value.
• How many times: The outer loop runs n times, and for each, the inner loop runs 5 times.

How Execution Grows With Input

As n grows, the total updates grow proportionally to n times 5.

Input Size (n)	Approx. Operations
10	10 x 5 = 50
100	100 x 5 = 500
1000	1000 x 5 = 5000

Pattern observation: The total work grows directly with n, multiplied by a fixed number 5.

Final Time Complexity

Time Complexity: O(n)

This means the work grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity must be quadratic O(n²)."

[OK] Correct: The inner loop runs a fixed 5 times, not depending on n, so it does not multiply n by itself.

Interview Connect

Understanding how nested structures affect time helps you explain code efficiency clearly and confidently.

Self-Check

"What if the inner array size changed from 5 to n? How would the time complexity change?"

Practice

1. What is the main purpose of using nested structures in C++?

easy

A. To allow structures to inherit functions

B. To create multiple inheritance between classes

C. To increase the size of a structure unnecessarily

D. To group related data logically inside another structure

Solution

1. Step 1: Understand nested structures concept

   Nested structures let you put one structure inside another to group related data logically.

2. Step 2: Compare options

   Only To group related data logically inside another structure correctly describes grouping data logically. Other options describe unrelated concepts.

3. Final Answer:

   To group related data logically inside another structure -> Option D

4. Quick Check:

   Nested structures = group data logically [OK]

Hint: Think of nested structures as folders inside folders [OK]

Common Mistakes:

• Confusing nested structures with inheritance
• Thinking nested structures increase structure size unnecessarily
• Assuming nested structures add functions

2. Which of the following is the correct syntax to access member city inside a nested structure address within person?

easy

A. person->address.city

B. person.address.city

C. person.address->city

D. person->address->city

Solution

1. Step 1: Identify access operator for nested structures

   When accessing members of nested structures by variable (not pointer), use dot operator for each level.

2. Step 2: Apply to given example

   Since person is a variable, access address with dot, then city with dot: person.address.city.

3. Final Answer:

   person.address.city -> Option B

4. Quick Check:

   Use dot for nested struct members when variable, not pointer [OK]

Hint: Use dot operator for nested struct members if not pointers [OK]

Common Mistakes:

• Using arrow operator (->) when variable is not a pointer
• Mixing dot and arrow operators incorrectly
• Trying to access nested member directly without parent

3. What will be the output of the following code?

struct Date {
  int day;
  int month;
};
struct Event {
  char name[10];
  Date date;
};

int main() {
  Event e = {"Party", {25, 12}};
  std::cout << e.name << " on " << e.date.day << "/" << e.date.month << std::endl;
  return 0;
}

medium

A. Party on 25/12

B. Party on 12/25

C. Compilation error

D. Party on 0/0

Solution

1. Step 1: Understand structure initialization

   Event e is initialized with name "Party" and Date with day=25, month=12.

2. Step 2: Trace output statement

   Output prints e.name, then e.date.day (25), then e.date.month (12) separated by slashes.

3. Final Answer:

   Party on 25/12 -> Option A

4. Quick Check:

   Nested struct initialized correctly = Party on 25/12 [OK]

Hint: Match initialization order with nested structure fields [OK]

Common Mistakes:

• Swapping day and month values
• Assuming compilation error due to nested struct
• Forgetting to use dot operator to access nested members

4. Identify the error in the following code snippet:

struct Point {
  int x, y;
};
struct Rectangle {
  Point topLeft;
  Point bottomRight;
};

int main() {
  Rectangle rect;
  rect.topLeft->x = 0;
  rect.topLeft->y = 10;
  return 0;
}

medium

A. Using arrow operator (->) on a non-pointer structure variable

B. Missing semicolon after struct definitions

C. Incorrect member names in Rectangle

D. Rectangle struct cannot contain Point structs

Solution

1. Step 1: Check member access operators

   rect.topLeft is a structure variable, not a pointer, so dot operator (.) must be used, not arrow (->).

2. Step 2: Identify error cause

   Using -> on non-pointer causes compilation error.

3. Final Answer:

   Using arrow operator (->) on a non-pointer structure variable -> Option A

4. Quick Check:

   Use dot for struct variables, arrow for pointers [OK]

Hint: Use dot for struct variables, arrow only for pointers [OK]

Common Mistakes:

• Confusing dot and arrow operators
• Assuming arrow works for all struct members
• Ignoring compiler error messages

5. Given the following nested structures, how would you write a function printBookInfo that prints the book title and the author's city?

struct Author {
  char name[50];
  char city[30];
};
struct Book {
  char title[100];
  Author author;
};

hard

A. void printBookInfo(Book b) { std::cout << b.title << ", " << b.author->city << std::endl; }

B. void printBookInfo(Book b) { std::cout << b.title << ", " << b.city << std::endl; }

C. void printBookInfo(Book b) { std::cout << b.title << ", " << b.author.city << std::endl; }

D. void printBookInfo(Book b) { std::cout << b->title << ", " << b->author.city << std::endl; }

Solution

1. Step 1: Understand structure member access

   Book variable b has member title and nested structure author. Access author.city with dot operator.

2. Step 2: Check each option

   void printBookInfo(Book b) { std::cout << b.title << ", " << b.author.city << std::endl; } correctly uses b.title and b.author.city with dot operators. Others misuse arrow or omit author.

3. Final Answer:

   void printBookInfo(Book b) { std::cout << b.title << ", " << b.author.city << std::endl; } -> Option C

4. Quick Check:

   Access nested struct members with dot: b.author.city [OK]

Hint: Use dot operator for nested struct members in function parameters [OK]

Common Mistakes:

• Using arrow operator on non-pointer parameter
• Skipping nested struct name when accessing member
• Using pointer syntax incorrectly