Understanding expected time bound for unsuccessful search in R-way tries As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please explain how this number can be derived?
search in a binary search tree is log base 2 of N. Now you have a R-nary tree, so the running time would be log base R of N.