Time complexity of DFS on graph (O(V+E)) vs DFS on matrix (3^(M*N))

user_2617765 0
Viewed 1135

Apologies if it sounds too illogical.

While solving some of the competitive questions today, a weird thought came across my mind.

We say time complexity of DFS is O(V+E) because we traverse the adjacency list only once i.e for every node we consider its edges.

However when performing dfs on matrix of size MN. A matrix we can say, is a graph with MN vertices (every cell is a vertex) and there is an edge to its neighbouring cell ==> every vertex have 4 edges (lets ignore border cases for simplicity)

Then while we do DFS

    private void dfs(int grid[][], int i, int j, int m, int n) {
        if(i<0 || j<0 || i>m || j>n || visited[i][j])
            return;
        visited[i][j] = true;
        dfs(grid, i+1, j, m, n);
        dfs(grid, i-1, j, m, n);
        dfs(grid, i, j-1, m, n);
        dfs(grid, i, j+1, m, n)
        visited[i][j] = false;
    }

==> in graph terminology its O(V+E) => O(MN + 4MN) => O(5MN) => O(MN) ==> But time complexity is 4^(MN)

Where does this analogy goes wrong?

backtracking depth-first-search time-complexity algorithm
1 Answers

The complexity of O(V+E) holds good only if each node is visited once. In your code you visit a node and mark it as visited but after parent is done, you are marking it as not visited.

So when the next child is processed, it will visit its parent again. If a parent has 4 children it will be visited by its children 1 extra time, making it 4 visits for each node and complexity is 4x4x...(MN) = 4^MN.

You remove visited[i][j] = false, and you will see that a node once visited is never visited again and complexity is O(number of nodes) = O(MN)

user_14103030
Related