1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It's not self-contained, it doesn't say what you tried, and it doesn't say what confused you about what you tried. For instance, did you look at the book itself, not just the slides? It's also arguably not on-topic for this SE. $\endgroup$ – jbapple Jan 14 '14 at 3:10
  • $\begingroup$ jbapple's comment still applies: have you checked the book? What have you tried towards showing the bound? Do you follow the case $R=2$? $\endgroup$ – Raphael Feb 6 '14 at 16:22
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy