Why arrays are needed in C++ - Performance Analysis

Time Complexity: Why arrays are needed

O(n)

Understanding Time Complexity

Arrays help us store many items together in one place. Understanding their time complexity shows how fast we can access or change these items.

We want to know how the time to do tasks with arrays changes as the number of items grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int findValue(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
    

This code searches for a target value in an array by checking each item one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop through the array elements one by one.
• How many times: Up to n times, where n is the number of items in the array.

How Execution Grows With Input

As the array gets bigger, the number of checks grows roughly the same way.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The time to find the value grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "Searching an array always takes the same time no matter how big it is."

[OK] Correct: Because the program may need to check many items, the time grows as the array gets bigger.

Interview Connect

Knowing how arrays work and their time cost helps you explain why we choose them and how to use them well in real coding tasks.

Self-Check

"What if we used a sorted array and binary search instead? How would the time complexity change?"