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, May 20 '17 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, May 21 '17 at 00: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, May 21 '17 at 00: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, May 21 '17 at 03:20

score 2 · Answer 1 · answered May 21 '17 at 00:45

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)

Leetcode : Time complexity for bfs/dfs

1 Answers1