merge sort recursion tree height
Posted
by Tony
on Stack Overflow
See other posts from Stack Overflow
or by Tony
Published on 2010-04-19T19:52:41Z
Indexed on
2010/04/19
19:53 UTC
Read the original article
Hit count: 390
Hello!
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 get 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!
© Stack Overflow or respective owner