Time complexity of c++ array loop

Question

i have the following loop but am unable to calculate the complexity .I need help

int A[n][n];
for(int i=0; i<n;i++) {
    for(int j=0;j<n;j++) {
        int x;
        cin >> x;
        A[i][j] = x;
    }
}
int sumLine = 0;
for(int k=0;k<n;k++) {
    sumLine += A[k][0];
}

i would appreciate

Double nested loop, each goes from `0` to `n`. Complexity -- `O(n^2)`. — PaulMcKenzie, Mar 29 '17 at 04:24

score 2 · Answer 1 · answered Mar 29 '17 at 04:28

You have three loops that you need to analyze. The first two are a set of nested loops: every time the inner (j) loop runs n times, the outer (i) loop runs once. Because the outer loop eventually runs n times, the whole set will run n*n = n^2 times, so we say that set of loops runs in O(n^2) time. Once these loops complete, the third (k) loop runs n times, which is O(n) time.

When you have two separate operations with different big-O complexities and want to add the complexities together to get their total, you take the larger of the two. Since O(n^2) is "larger" than O(n), we say that the entire program runs in O(n^2) time.

score 0 · Answer 2 · edited May 23 '17 at 11:54

0

Time complexity will be O(n^2). Read more about time complexity here - How to find time complexity of an algorithm . It has some good explanation here.

edited May 23 '17 at 11:54

Community

1
1

answered Mar 29 '17 at 04:25

Harshit

1,510
19
42

Time complexity of c++ array loop

2 Answers2