Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. Artificial Intelligence, 62 (41--78), 1993. In fact, RBFS is much more than "just updating the $F(n)$ value for the parent for which the current execution was stopped". RBFS stores the so-called stored $f$-value of each node $n$ as $F(n)$. An invariant of the algorithm is that the stored $f$-value is the minimum static $f$-value (ie., the usual $f(n)=g(n)+h(n)$) among all leave nodes generated in a tree rooted at $n$. From here, $F(n)\geq f(n)$ for all nodes $n$ given that costs are monotonic. Initially, when a node is expanded for the first time $F(n)=f(n)$. Later on, when backtracking after examining its descendants, its $F$-value (ie., the stored $f$-value) is accordingly updated.
So, if nodes beneath node $n$ are examined, up to what point are they developed? Another parameter used in RBFS is an upper bound $B$ which is initially set to $+\infty$. Do not read $B$ as a global upper bound! Indeed, every time a node is selected for expansion, $B$ is updated to the minimum between the current value of $B$ and the second-best $F$-value. So here you are a second invariant of RBFS: every time a node is selected for expansion, it has an $f$-value which is less or equal than the second best $f$-value in the whole search tree. This is true: first, because $B$ is updated using the second-best $F$-value which amounts to compare it with all the descendants of its siblings; second, the other component used is $B$ itself which was, in turn, computed in the same way by its ancestors. Finally, remember that after every expansion, nodes are sorted in increasing order of their $F$-value.
As a result, RBFS expands nodes in the same order of A*! So far, I do not see it as a successor of IDA*, but instead, as a new member of the large family of best-first search algorithms. Note that in the preceding statement I solely refer to the new expansions. There will be often in between an arbitrarily large number of re-expansions.
For a more didactical explanation of the algorithm refer to the paper Ariel Felner. The Collapse Macro in Best-First Search Algorithms and and Iterative Variant of RBFS. Symposium on Combinatorial Search (SoCS 2015), 28--34. Israel, 2015. During his dissertation Ariel openly said that this is an algorithm poorly understood in general and there was agreement. Conclusion: read this paper also if you are interested in understanding RBFS (I do sincerely doubt that my review suffices for a good understanding of the algorithm).
Regarding your questions:
- Note that in the first paragraph I expliclty refered to backtracking ie, RBFS is implemented as a depth-first search algorithm. So far, its memory requirements are $O(bd)$ where $b$ is the branching factor and $d$ is the depth where the solution lies.
- Assuming that the expansion of every node is the dominant operation and that it takes the same amount of time in spite of the node been expanded, then the number of expansions directly relates to the time complexity. Korf proved that, in the general case, the time complexity is (as one would expect) $O(bˆd)$ where $b$ is the asymptotic branching factor. Also, the best and worst case analysis are analyzed by Korf in the original paper.
As you mentioned the relationship with IDA* let me also remark that Korf proved that RBFS expands less nodes (in total, considering also re-expansions) than IDA* in the average-case in case of monotonic costs. If costs do not grow monotonically then these algorithms cannot be compared as they traverse entirely different search trees. Since IDA* is known to be asymptotically optimal, then RBFS is asymptotically optimal as well.
Hope this helps,
