Nested structures - Time & Space Complexity

Time Complexity: Nested structures

O(n)

Understanding Time Complexity

When working with nested structures in C, it's important to see how the program's work grows as the data size grows.

We want to know how the time to process nested structures changes when the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    int x;
    int y;
};

struct Rectangle {
    struct Point corners[4];
};

void printRectangles(struct Rectangle rects[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            printf("(%d, %d) ", rects[i].corners[j].x, rects[i].corners[j].y);
        }
        printf("\n");
    }
}

This code prints the coordinates of each corner of multiple rectangles stored in an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop prints 4 corners for each rectangle.
• How many times: The outer loop runs n times, and for each, the inner loop runs 4 times.

How Execution Grows With Input

As the number of rectangles (n) grows, the total prints grow proportionally because each rectangle always has 4 corners.

Input Size (n)	Approx. Operations
10	40 (10 x 4)
100	400 (100 x 4)
1000	4000 (1000 x 4)

Pattern observation: The total work grows directly with n, since the inner loop count is fixed.

Final Time Complexity

Time Complexity: O(n)

This means the time to print all rectangles grows in a straight line as the number of rectangles 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 4 times, not depending on n, so it does not multiply n by n.

Interview Connect

Understanding how nested structures affect time helps you explain your code clearly and shows you can think about efficiency in real projects.

Self-Check

"What if the number of corners in each rectangle was not fixed at 4 but depended on input size m? How would the time complexity change?"

Practice

1. What is a nested structure in C programming?

easy

A. A structure that contains another structure as a member

B. A structure with only one member

C. A structure declared inside a function

D. A structure that uses pointers only

Solution

1. Step 1: Understand structure composition

   A nested structure means one structure is included inside another as a member.

2. Step 2: Rule out distractors

   The other options describe unrelated concepts: a structure using pointers only, with only one member, or declared inside a function.

3. Final Answer:

   A structure that contains another structure as a member -> Option A

4. Quick Check:

   Nested structure = structure inside structure [OK]

Hint: Nested means one structure inside another [OK]

Common Mistakes:

• Thinking nested means pointer usage
• Confusing nested with single-member structures
• Assuming nested means declared inside functions

2. Which of the following is the correct syntax to access a member of a nested structure in C?

easy

A. outer.inner->member

B. outer->inner->member

C. outer.inner.member

D. outer->inner.member

Solution

1. Step 1: Identify access operator for nested structures

   When using nested structures (not pointers), use dot notation for each level: outer.inner.member.

2. Step 2: Understand pointer vs non-pointer access

   Arrow (->) is used only when accessing members through pointers, which is not stated here.

3. Final Answer:

   outer.inner.member -> Option C

4. Quick Check:

   Use dot for nested struct members [OK]

Hint: Use dot notation for nested struct members [OK]

Common Mistakes:

• Using arrow (->) when not using pointers
• Mixing dot and arrow incorrectly
• Confusing member access syntax

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

typedef struct {
    int day;
    int month;
    int year;
} Date;

typedef struct {
    char name[20];
    Date birthday;
} Person;

int main() {
    Person p = {"Alice", {15, 8, 1990}};
    printf("%d-%d-%d", p.birthday.day, p.birthday.month, p.birthday.year);
    return 0;
}

medium

A. 15-8-1990

B. Alice-15-8

C. 1990-8-15

D. Compilation error

Solution

1. Step 1: Understand structure initialization

   Person p is initialized with name "Alice" and birthday as Date {15, 8, 1990}.

2. Step 2: Trace printf output

   printf prints p.birthday.day (15), p.birthday.month (8), p.birthday.year (1990) separated by dashes.

3. Final Answer:

   15-8-1990 -> Option A

4. Quick Check:

   Print nested struct members correctly [OK]

Hint: Access nested members with dot notation [OK]

Common Mistakes:

• Printing name instead of date
• Mixing order of day, month, year
• Forgetting to initialize nested struct

4. Identify the error in this nested structure code snippet:

struct Address {
    char city[20];
    int zip;
};

struct Employee {
    char name[30];
    struct Address addr;
};

int main() {
    struct Employee emp;
    emp.addr->zip = 12345;
    return 0;
}

medium

A. Missing semicolon after struct definitions

B. Using '->' operator on a non-pointer structure variable

C. Incorrect declaration of nested structure

D. Cannot assign integer to zip member

Solution

1. Step 1: Check member access syntax

   emp.addr is a structure variable, not a pointer, so '->' operator is invalid here.

2. Step 2: Correct operator usage

   Use dot operator '.' to access zip: emp.addr.zip = 12345;

3. Final Answer:

   Using '->' operator on a non-pointer structure variable -> Option B

4. Quick Check:

   Use '.' for struct variables, '->' for pointers [OK]

Hint: Use '.' for struct, '->' only for pointers [OK]

Common Mistakes:

• Using '->' on struct variables
• Confusing pointer and non-pointer access
• Ignoring compiler error messages

5. Given the following nested structures, how would you write a function in C that takes a Person and returns the birth year?

typedef struct {
    int day;
    int month;
    int year;
} Date;

typedef struct {
    char name[50];
    Date birthday;
} Person;

// Function prototype here

Which of the following is the correct function definition?

hard

A. int getBirthYear(Person *p) { return p.birthday->year; }

B. int getBirthYear(Person *p) { return p->birthday.year; }

C. int getBirthYear(Person p) { return p.year; }

D. int getBirthYear(Person p) { return p.birthday.year; }

Solution

1. Step 1: Understand parameter passing

   The function takes a Person by value, so use dot notation to access members.

2. Step 2: Access nested member correctly

   Access birthday.year as p.birthday.year since p is not a pointer.

3. Final Answer:

   int getBirthYear(Person p) { return p.birthday.year; } -> Option D

4. Quick Check:

   Use dot for struct value parameters [OK]

Hint: Use dot for struct, arrow for pointer parameters [OK]

Common Mistakes:

• Using arrow (->) on non-pointer parameter
• Accessing wrong member name
• Confusing pointer and value parameter syntax