CODEWITHSUNDEEP
depth-first-searchbreadth-first-search
Gowtham Ganesh
Gowtham Ganesh

Reputation: 340

Leetcode : Time complexity for bfs/dfs

As per my understanding, both DFS and BFS take O(V+E). But is it possible for the search algorithms to have different time complexities?

For example, in this problem (https://leetcode.com/problems/kill-process/#/description) using DFS takes longer than BFS.

BFS:

class Solution(object):
    def bfs(self, pid, ppid, tmp, output):
        child = []
        for i in xrange(len(ppid)):
            if ppid[i] in tmp:
                output.append(pid[i])
                child.append(pid[i])    

        if child != []:
            self.bfs(pid, ppid, child, output)


    def killProcess(self, pid, ppid, kill):
        """
        :type pid: List[int]
        :type ppid: List[int]
        :type kill: int
        :rtype: List[int]
        """
        output, tmp = [kill], [kill]
        self.bfs(pid, ppid, tmp, output)
        return output

Time complexity: O(NlgN)

DFS:

class Solution(object):
    def dfs(self, pid, ppid, kill, output):
        for i in xrange(len(ppid)):
            if ppid[i] == kill:
                if kill not in output:
                    output.append(kill)
                self.dfs(pid, ppid, pid[i], output)
        if kill not in output:
            output.append(kill)


    def killProcess(self, pid, ppid, kill):
        """
        :type pid: List[int]
        :type ppid: List[int]
        :type kill: int
        :rtype: List[int]
        """
        output = []
        self.dfs(pid, ppid, kill, output)
        return output

Time complexity: O(N^2)

Upvotes: 0

Views: 853

Answers (1)

Raghavendra Bableshwar
Raghavendra Bableshwar

Reputation: 211

First of all, the complexity of algorithms depend upon the data structures used. The complexity of BFS and DFS are O(V+E) only when you use adjacency list representation of graph.

Secondly, the code does not maintain a visited set of nodes which is referenced to backtrack, and not to re-visit the same nodes.

Hence the complexity of your code is O(n^2) and not O(V+E)

Upvotes: 2

Related Questions