CODEWITHSUNDEEP
c++algorithmtime-complexity
adam
adam

Reputation: 37

what is the Time complexity of this function

How to calculate time complexity of this function step by step ?

This function converts an adjacency list to a matrix, manipulate the matrix and then convert the matrix back to a list

Graphe *Graphe::grapheInverse( void ){
    
    Graphe *r = new Graphe (_adjacences.size() );
    
    std::vector<vector<int> > matrix(_adjacences.size(), vector<int>( _adjacences.size() ) );
    
    std::vector<vector<int> > liste(matrix.size());

    for (unsigned i = 0; i < _adjacences.size(); i++)
        for (auto j : *_adjacences[i])
            matrix[i][j] = 1;


    for (int i = 0; i < matrix.size(); i++) { 
        for (int j = 0; j < matrix[i].size(); j++) {
            if (matrix[i][j] == 1)
                matrix[i][j] = 0;
            else 
                matrix[i][j] = 1;
            if (i == j)
                matrix[i][j] = 0;
        }
    }


    for (int i = 0; i < matrix.size(); i++){
        for (int j = 0; j < matrix[i].size(); j++){
            if (matrix[i][j] == 1){
                liste[i].push_back(j);
            }
        }
    }


    for (int i = 0; i < liste.size(); i++) { 
        for (int j = 0; j < liste[i].size(); j++) {
            r->ajouterArcs( i, liste[i][j] );        
        }
    }

    return r;
}

Upvotes: 0

Views: 87

Answers (1)

samsonjm
samsonjm

Reputation: 270

Note that the following all applies to big-O time complexity:

Calculating the time complexity involves looking at how many times you iterate over the data. One for loop is N, as you touch each point once. A nested for loop (for i in data, for j in data) is N^2 because you touch each point once for each point there is.

A for loop next to a for loop (For i in data do X, for i in data do Y) touches the data N + N times. This is still considered N time complexity because as N approaches a very large number, 2N doesn't make much difference. The same goes for nested loops, N^2+N^2 = 2N^2 -> Essentially, you would ignore any multipliers, and go based on the times you touch N. That means 2N^2 changes to N^2

To reiterate, this is specifically for big-O time complexity

Upvotes: 3

Related Questions