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: 392

Filed under:

recursion

|

trees

|

computer-science

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

Related posts about recursion

tail recursion vs. forward recursion

as seen on Stack Overflow - Search for 'Stack Overflow'
Can someone give me the difference between these two kinds recursions and example? specifically in ocaml. Thanks >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More
Python recursive function error: "maximum recursion depth exceeded"

as seen on Stack Overflow - Search for 'Stack Overflow'
I solved Problem 10 of Project Euler with the following code, which works through brute force: def isPrime(n): for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def primeList(n): primes = [] for i in range(2,n): if isPrime(i): … >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
How does the recursion here work?

as seen on Stack Overflow - Search for 'Stack Overflow'
code 1: public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } how can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand… >>> More

Related posts about trees

Paged binary trees vs. AVL trees and B-trees

as seen on Stack Overflow - Search for 'Stack Overflow'
How are paged binary trees different from AVL trees and B-trees? >>> More
Minimum and maximum height of binary search trees, 2-3-4 trees and B trees.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, note this is not homework. But can anyone tell me how you find the min/max height of B trees, 2-3-4 trees and binary search trees? Thanks >>> More
Difference between B Trees and 2-3-4 Trees

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, Could someone please explain to me the difference between B Trees and 2-3-4 Trees? And also how would you find the maximum and minimum height of each? Thanks >>> More
B- trees, B+ trees difference

as seen on Stack Overflow - Search for 'Stack Overflow'
In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only. Is there any advantage of doing the above in a B+ tree? Why not use B- trees instead of B+ trees everywhere? As intuitively they seem much faster. I mean why… >>> More
What is the usage of Splay Trees in the real world?

as seen on Programmers - Search for 'Programmers'
I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html I read that splay trees are 'A good example is a network router'… >>> More