What is the complixety of turning a sorted array of size n to a legal 2-4 B tree?
What would it be if the array wasn't sorted.
I believe that the first answer should be O(logn) (As many splits that we'll have to do) and the second answer should be O(nlogn+logn)=O(nlogn), because of the sorting.
Thank you.
You can definitely convert a sorted array into a 2-4 tree in O(n) time. See Ralf Hinze's Constructing Red-Black Trees for details. His algorithms are written in terms of red-black trees, but red-black trees are essentially the same as 2-4 trees (a black node with two black children is a 2 node, a black node with one red child is a 3 node, and a black node with two red children is a 4 node).
And, yes, if the array is unsorted, you are going to be stuck with O(n log n) time (unless you know something special about the data that lets you sort it in better than O(n log n) time).