|Don't ask to ask, just ask|
Re^5: Finding All Paths From a Graph From a Given Source and End Nodeby BrowserUk (Pope)
|on Nov 01, 2010 at 09:37 UTC||Need Help??|
What's the time complexity of findPaths()?
Um... O(lots) :). Honestly, I haven't got a clue how you go about assessing that.
It will be entirely dependant upon the complexity of the graph. Not just the number of nodes, but the number of connections at each node. And I don't have the math to make that kind of assessment.
I'd say that if your graphs are big enough for you to worry about it, then you'd probably be better of looking at an iterative solution rather than a recursive. Though often, iterative solutions that just emulate the recursion through manual stack handling are no more efficient, and often much less so.
I think the main cost of my routine is the memory allocations for the results sets. If your application only need to process one results set at a time, rather than having them all available, then I'd be looking for an iterator solution.
FWIW (which is not much IMO), the literature says that breadth-first and depth-first are both O(Bd) worst case.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.