Can someone explain the time complexity of backtracking/BFS method for this problem


  • 0
    B

    can someone explain the time complexity of backtracking/BFS method for this problem


  • 0
    L

    BFS
    Time complexity is O(|V|) where |V| is the number of nodes,you need to traverse all nodes.
    Space complecity is O(|V|) as well - since at worst case you need to hold all vertices in the que.

    Backtrack
    The running time of your algorithm is at most N(N−1)(N−2)⋯(N−K+1), i.e., N!/(N−K)!. This is O(NK), i.e., exponential in K.

    Justification: There are N possible choices for what you put into the first blank, and in the worst case you might have to explore each. There are N−1 choices for the second blank, and so on. You can draw a tree of the choices made: the first level shows the choice of what to put in the first blank, the second level shows the choice of what to put in the second blank, and so on. The degree of the root is N; the degree of the nodes at the second level is N−1; and so on. The number of leaves is the product of the degrees at each level, i.e., N(N−1)(N−2)⋯(N−K+1). In the worst case, your algorithm might have to explore every possible node in this tree (if it is not able to stop early before reaching the Kth level and backtrack from a higher-up node). Therefore, this is a valid upper bound for the running time of your algorithm.

    If you want a tighter analysis, here is the exact worst-case running time (not an upper bound). The number of leaves in your search tree, in the worst case, is the number of strictly increasing sequences of length K over {1,…,N} that start with 0. (We can assume without loss of generality that the first blank contains a 0, as you point out, which is why we can restrict to sequences that start with a 0.) That number is exactly C(N−1,K−1)=(N−1)!/((K−1)!(N−K)!).

    This is a tighter analysis, but it doesn't save us from exponential running time. When N≫K, C(N−1,K−1) is still O(NK), i.e., exponential in K.

    That said, evaluating your algorithm experimentally (by testing it on some real data sets) would probably be a better way to evaluate your algorithm than trying to derive a worst-case running time. You might want to compare it to the performance of translating your problem into a SAT instance and using an off-the-shelf SAT solver. Depending upon the value of N and K, there might be other better alternatives as well.


Log in to reply
 

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