Data members and member functions in C++ - Time & Space Complexity

Time Complexity: Data members and member functions

O(1)

Understanding Time Complexity

We want to understand how the time taken by a program changes when it uses data members and member functions in a class.

Specifically, we ask: How does the program's running time grow as the size of data changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Sample {
  int data[100];
public:
  void fillData() {
    for (int i = 0; i < 100; i++) {
      data[i] = i * 2;
    }
  }
  int getData(int index) {
    return data[index];
  }
};

This code defines a class with a fixed-size array and two member functions: one fills the array, the other returns a value at a given position.

Identify Repeating Operations

Look for loops or repeated actions inside the member functions.

• Primary operation: The for-loop inside fillData() that sets each element.
• How many times: Exactly 100 times, once for each element.

How Execution Grows With Input

Since the array size is fixed at 100, the number of operations stays the same no matter what.

Input Size (n)	Approx. Operations
10	100 (fixed)
100	100 (fixed)
1000	100 (fixed)

Pattern observation: The time does not grow with input size because the array size is constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to run these member functions stays the same no matter how big the input might be.

Common Mistake

[X] Wrong: "Since there is a loop, the time must grow with input size."

[OK] Correct: The loop runs a fixed number of times (100), so it does not depend on input size and the time stays constant.

Interview Connect

Understanding how member functions and data members affect time helps you explain how your code behaves in real projects.

Self-Check

"What if the array size was a variable passed to the class instead of fixed? How would the time complexity change?"