Time Complexity: What is C++
O(n)
0
0
What is C++ - Complexity Analysis
Understanding Time Complexity
When learning about C++, it helps to understand how the time a program takes can grow as it works with more data.
We want to see how the steps a C++ program does change when the input gets bigger.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
#include <iostream>
using namespace std;
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 size n.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The for-loop that adds each number in the array.
- How many times: It runs once for each item 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 size of the input.
Final Time Complexity
Time Complexity: O(n)
This means if you double the input size, the time to finish roughly doubles too.
Common Mistake
[X] Wrong: "The loop runs a fixed number of times no matter the input size."
[OK] Correct: The loop depends on n, so bigger input means more steps.
Interview Connect
Understanding how loops affect time helps you explain how your C++ code will behave with different input sizes.
Self-Check
"What if we used two nested loops to sum pairs of numbers? How would the time complexity change?"