Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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
    }
}
like image 427
J. Woodring Avatar asked Jan 27 '14 18:01

J. Woodring


People also ask

What is O and n in time complexity?

Linear Time Complexity: O(n) When time complexity grows in direct proportion to the size of the input, you are facing Linear Time Complexity, or O(n). Algorithms with this time complexity will process the input (n) in “n” number of operations.

How do you explain time complexity?

Time Complexity: The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Note that the time to run is a function of the length of the input and not the actual execution time of the machine on which the algorithm is running on.

What does O'n mean in programming?

O(n) is Big O Notation and refers to the complexity of a given algorithm. n refers to the size of the input, in your case it's the number of items in your list. O(n) means that your algorithm will take on the order of n operations to insert an item.

What does Big O of n mean?

Big-O Definition O stands for Order Of , so O(N) is read “Order of N” — it is an approximation of the duration of the algorithm given N input elements.


1 Answers

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

like image 111
Navin Avatar answered Sep 28 '22 00:09

Navin