I've read in a few places (a book I have and online articles) that the running time of Depth-First search is (O(|V| + |E|)), which is linear. In my implementation, I use it to solve the Traveling Salesman Problem, and the running time of Depth-first search grows exponentially, not linear.

Wikipedia notes the time as (O(|V| + |E|)), and I noticed on the side it says O(|V|+|E|) = O(b^d).

http://en.wikipedia.org/wiki/Depth-first_search

Can someone please explain this?

Also, doesn't depth-first search traverse all possible paths? So, it will guarantee that the optimal path is found. I've been looking for documentation to confirm this, but I haven't found any yet. In my understanding, it does search all paths. My implementation seems to confirm this.

Thanks.