开发者

merge sort recursion tree height

开发者 https://www.devze.com 2022-12-27 05:14 出处：网络

I am learning about recursion tree\'s and trying to figure out how the height of the tree is log b of n where n = 2 and one has 10 elements as input size. I am working with Merge sort.

相关专题：computer-science recursion tree

I am learning about recursion tree's and trying to figure out how the height of the tree is log b of n where n = 2 and one has 10 elements as input size. I am working with Merge sort.

The number of times the split is done is the height of the tree as far as I understood, and the number of levels in the tree is height + 1.

But if you take (for merge sort) log2 of 10 you g开发者_运维技巧et 1, where if you draw the tree you get at least 2 times that the recursion occurs.

Where have I gone wrong? (I hope I am making sense here)

NOTE: I am doing a self study, this is not homework!

log₂(10) = 3.321928094887362...

In any case, the recursive call depth is O(log(n)), which basically means "on the order of log(n)". The actual call depth for an O(log(n)) algorithm might be k*log(n)+c, or even k*log(n)+α(n)/log(log(n))+c.