Leetcode : Time complexity for bfs/dfs

Question

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)

What is the type of ppid? I see you're passing-in ppid in each recursive call which is then iterated-over on each node visit - that's inefficient and not inherent in any DFS algorithm implementation. — Dai
– Dai, Commented May 20, 2017 at 23:01
@Dai Thanks! ppid is a list. Btw, since I dont go over the same path again (eventhough ppid is iterated over and over again at each recursive call), isnt this still DFS? — Gowtham Ganesh
– Gowtham Ganesh, Commented May 21, 2017 at 0:23
Your code is not DFS because you're iterating over a list, not visiting nodes in a tree (your code doesn't have any concept of a node's children), and on every iteration you're looping through the ppid list, hence the O(n^2) runtime complexity. Your use of the in output operator will also iterate over output in O(n) time (I believe - I'm not too well-versed in Python) - you should use a hashset or hashmap (associative-array, dictionary) type for O(1) lookup instead. — Dai
– Dai, Commented May 21, 2017 at 0:31
@Dai Gotcha! The in operator takes just O(1) as python maintains an internal hashmap for each lists. Btw, I now get it where I'm going wrong: The ppid and pid lists has a tree structure so there is no need to have an additional "visited" node list. However, at each run the code iterates over the entire tree (ppid) to check for a particular node (pid) rather than parsing just a particular subtree. Thanks! Now, I'm curious how my BFS implementation takes just O(NlgN). I would be grateful if you could correct me incase I'm wrong with the time complexity calculation! — Gowtham Ganesh
– Gowtham Ganesh, Commented May 21, 2017 at 3:20

Raghavendra Bableshwar · Accepted Answer · 2017-05-21 00:45:29Z

2

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)

answered May 21, 2017 at 0:45

Raghavendra Bableshwar

2213 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Leetcode : Time complexity for bfs/dfs

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related