CODEWITHSUNDEEP
complexity-theory
J. Woodring
J. Woodring

Reputation: 111

Why is this time complexity O(n)?

Why does the below function have a time complexity of O(n)? I can't figure it out for the life of me.

void setUpperTriangular (
    int intMatrix[0,…,n-1][0,…,n-1]) {
        for (int i=1; i<n; i++) {
            for (int j=0; j<i; j++) {
                    intMatrix[i][j] = 0;
            } 
        }
    }
}

I keep getting the final time complexity as O(n^2) because: 

i: execute n times{//Time complexity=n*(n*1)
    j: execute n times{ //Time complexity=n*1
        intMatrix[i][j] = 0; //Time complexity=1
    }
}

Upvotes: 6

Views: 297

Answers (4)

Navin
Navin

Reputation: 4115

The code iterates through n^2/2 (half a square matrix) locations in the array, so its time complexity is O(n^2)

Upvotes: 9

Prabh_chandhar
Prabh_chandhar

Reputation: 1

It can be at most considered as O(n.m) which finally comes down to O(n.n) or O(n^2)..

Upvotes: 0

J. Woodring
J. Woodring

Reputation: 111

So, CS department head explained it a different way. He said that since the second loop doesn't iterate n times, it iterates n! times. So technically it is O(n).

Upvotes: 0

user918603
user918603

Reputation: 43

This is same as insertion sort's for loop. Time complexity of insertion sort is O(n2).

Upvotes: 1

Related Questions