Thursday, October 8, 2009

Q: What's the difference between time and space complexity?

Time complexity concerns the number of operations you have to perform to get to a goal state. We measure these usually in
b: the maximal branching factor,
m: the maximum depth of the search tree
d: the depth of the solution.

Space complexity on the other hand concerns the number of "things" you have to keep in memory during your search. For instance for BFS you keep all nodes in memory, so the complexity is O(b^[d+1]) which us the number of nodes you expand (or O(b^d), see blog below). For DFS you only keep the path to the current node in memory and potentially all its the successors of those nodes, so its O(bm).