Little bit confused about the time complexity here


  • 7
    W

    I think the time complexity of BFS and DFS are almost the same at the worst case, if we take care of the base case in recursion, we return as long as the current step is smaller than the cumulative one. Time(BFS) = Time(DFS) + 4mn

    I am confused about the time complexity here, what is the TC of DFS here, is it O((mn)^2)? If this is the worst case than what about the TC of BFS? Could someone help?...


  • 0
    A

    I was also confused with the time complexity.

    I thought the worst case for both methods are O((mn)^2), until I saw and thought carefully about the following solution.

    https://leetcode.com/discuss/60179/java-bfs-solution-o-mn-time

    It is really O(mn). Image each gate as the root of a tree, the queue could magically guarantee we traverse level by level of each trees.

    step 1: add each root node into the queue.

    step 2: pop a node(root) out, visit it is 1st level children(if has not been visited), add all 1st level children into the queue. then pop second node(root) out ...


  • 0
    S

    Can you explain why DFS takes O((mn)^2)? Thank you!


  • 0
    M
    This post is deleted!

  • 0

    See here for a benchmark.

    In worst case DFS is much slower than BFS and is not O(mn).

    For this problem, BFS is definitely the better solution.

    DFS is faster only for particular testcases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.