big o notation practice c++

Big O Notation Practice in C++

Consider the following C++ code:

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

1. Step 1: Identify the Operations

2. The function performs a single addition operation inside the loop, and the loop itself runs n times.

3. Step 2: Express the Time Complexity

4. The time complexity of the function can be expressed as O(n), where n is the size of the input array.

5. Step 3: Justification

6. The loop iterates through the entire input array, performing a constant-time operation (addition) at each iteration. As the number of elements in the input array increases, the number of iterations increases linearly, resulting in a linear time complexity of O(n).

7. Conclusion

8. The time complexity of the sum function is O(n), indicating that its runtime grows linearly with the size of the input array.