Comment Re:Traveling Salesman (Score 2, Informative) 309
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.
