Array of structures - Time & Space Complexity

Time Complexity: Array of structures

O(n)

Understanding Time Complexity

When working with an array of structures, it's important to know how the time to process them grows as the array gets bigger.

We want to understand how the number of operations changes when we access or loop through these structures.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    int x;
    int y;
};

void printPoints(struct Point points[], int n) {
    for (int i = 0; i < n; i++) {
        printf("(%d, %d)\n", points[i].x, points[i].y);
    }
}
    

This code loops through an array of Point structures and prints each point's coordinates.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each structure in the array.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the number of points increases, the total work grows directly with it.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: Doubling the number of points doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to process the array grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Accessing a structure inside an array is slower and adds extra loops."

[OK] Correct: Accessing each structure is done directly by index in one loop, so it does not add extra loops or slow down beyond the main loop.

Interview Connect

Understanding how looping through arrays of structures scales helps you explain and write efficient code when handling collections of data in real projects.

Self-Check

"What if we nested another loop inside to compare each point with every other point? How would the time complexity change?"

Practice

1. What is the correct way to declare an array of 5 structures named Student in C?

easy

A. Student arr[5];

B. struct Student arr;

C. Student arr;

D. struct arr[5];

Solution

1. Step 1: Understand structure array declaration

   To declare an array of structures, use the structure type followed by the array name and size in square brackets.

2. Step 2: Apply correct syntax for array of structures

   Since Student is the structure type, Student arr[5]; declares an array of 5 Student structures.

3. Final Answer:

   Student arr[5]; -> Option A

4. Quick Check:

   Array of structures = type name[size] [OK]

Hint: Use type name[size] to declare structure arrays [OK]

Common Mistakes:

• Forgetting 'struct' keyword if not typedefed
• Declaring single structure instead of array
• Using wrong syntax like struct arr[5];

2. Which of the following is the correct syntax to access the age member of the 3rd element in an array students of structures?

easy

A. students->age[3];

B. students.age[3];

C. students[3].age;

D. students[2].age;

Solution

1. Step 1: Understand zero-based indexing in arrays

   Arrays in C start at index 0, so the 3rd element is at index 2.

2. Step 2: Access structure member using dot operator

   Use students[2].age to access the age member of the 3rd element.

3. Final Answer:

   students[2].age; -> Option D

4. Quick Check:

   3rd element = index 2, use dot for member [OK]

Hint: Remember arrays start at 0; 3rd element is index 2 [OK]

Common Mistakes:

• Using index 3 instead of 2 for 3rd element
• Using arrow operator on array elements
• Accessing member as students.age[3]

3. Consider the code:

typedef struct {
  int id;
  char name[10];
} Item;

Item items[2] = {{1, "Pen"}, {2, "Book"}};

printf("%s", items[1].name);

What will be the output?

medium

A. Pen

B. Book

C. items[1].name

D. Compilation error

Solution

1. Step 1: Identify the array initialization

   The array items has two elements: first with id=1, name="Pen"; second with id=2, name="Book".

2. Step 2: Understand printf access

   items[1].name accesses the second element's name, which is "Book".

3. Final Answer:

   Book -> Option B

4. Quick Check:

   items[1].name = "Book" [OK]

Hint: Index 1 accesses second element's name [OK]

Common Mistakes:

• Confusing index 0 and 1
• Expecting id to print instead of name
• Syntax errors in initialization

4. What is wrong with this code snippet?

struct Point {
  int x, y;
};

struct Point points[3];
points[0].x = 10;
points[0].y = 20;
points[1].x = 30;
points[1].y = 40;
points[2].x = 50;
points[2].y = 60;

printf("%d", points[3].x);

medium

A. Array size should be 4 instead of 3

B. Missing semicolon after struct definition

C. Accessing points[3] is out of bounds

D. Incorrect struct member access syntax

Solution

1. Step 1: Check array size and indexing

   The array points has size 3, valid indices are 0, 1, 2.

2. Step 2: Identify invalid access

   Accessing points[3] is out of bounds and causes undefined behavior.

3. Final Answer:

   Accessing points[3] is out of bounds -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Array indices go from 0 to size-1 only [OK]

Common Mistakes:

• Using index equal to array size
• Ignoring array bounds errors
• Assuming array auto-expands

5. You have a structure Employee with members int id; and float salary;. How do you write a function in C that takes an array of Employee and its size, then returns the average salary?

hard

A. float averageSalary(Employee emp[], int n) { float sum=0; for(int i=0;i

B. float averageSalary(Employee *emp, int n) { float sum=0; for(int i=0;isalary; return sum/n; }

C. float averageSalary(Employee emp[], int n) { float sum=0; for(int i=0;i

D. float averageSalary(Employee emp[], int n) { float sum=0; for(int i=0;i

Solution

1. Step 1: Loop through array elements correctly

   Use a for loop from 0 to n-1 and access each element with emp[i].

2. Step 2: Sum the salary member of each element

   Access salary as emp[i].salary and add to sum, then divide by n.

3. Final Answer:

   float averageSalary(Employee emp[], int n) { float sum=0; for(int i=0;i -> Option A

4. Quick Check:

   Loop + emp[i].salary sum / n = average [OK]

Hint: Use emp[i].member to access array struct members [OK]

Common Mistakes:

• Using emp->salary inside loop instead of emp[i].salary
• Accessing emp.salary instead of emp[i].salary
• Adding whole struct instead of member