What are you talking about? DFS is only linear in the best case where the solution is on the first branch. If the depth of the tree is d then at the worst case you will have to search every node which would be 2^(d+1) - 1 nodes. That's exponential time.
Slashdot Mirror
What are you talking about? DFS is only linear in the best case where the solution is on the first branch. If the depth of the tree is d then at the worst case you will have to search every node which would be 2^(d+1) - 1 nodes. That's exponential time.