Built-in data types in C++ - Time & Space Complexity

Time Complexity: Built-in data types

O(n)

Understanding Time Complexity

Let's explore how the time it takes to work with built-in data types changes as the size of the data grows.

We want to know how operations on these types scale when we use them in code.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}
    

This code adds up all the numbers in an array of integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each element of the array to the sum.
• How many times: Once for each element in the array, so n times.

How Execution Grows With Input

As the array gets bigger, the number of additions grows in the same way.

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

Pattern observation: The work grows directly with the number of items; double the items, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the task grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Adding elements to a built-in type like int is constant time, so the whole function is constant time."

[OK] Correct: While adding two numbers is quick, the function adds each element one by one, so the total time depends on how many elements there are.

Interview Connect

Understanding how simple operations scale helps you explain your code clearly and shows you know how programs behave with bigger data.

Self-Check

"What if we used a nested loop to sum elements in a 2D array? How would the time complexity change?"