I am implementing 2-3-4 tree for some kind of memory managment.During init of my application I want to insert there some number of integers (get it as input - say n) What is a complexity of such an insert? O(nloglog(n))?
The complexity of the insertion on a 2-3-4 tree is O(log(n)).
We can see a quota from Wikipedia
2–3–4 trees are B-trees of order 4 (Knuth 1998)
The complexity of insertion on B-tree is O(log(n)), so is the 2-3-4 tree. By repeating inserting to initialize the 2-3-4 tree, we may say the time cost of init is O(n*log(n)). But we can expect a special way to construct [link]:
In applications, it is frequently useful to build a B-tree to represent a large existing collection of data and then update it incrementally using standard B-tree operations. In this case, the most efficient way to construct the initial B-tree is not to insert every element in the initial collection successively, but instead to construct the initial set of leaf nodes directly from the input, then build the internal nodes from these. This approach to B-tree construction is called bulkloading. Initially, every leaf but the last one has one extra element, which will be used to build the internal nodes.
The time cost may be (n + n/4 + n/16 + ... + n/(4^h)). Based on the sum of Geometric Progression. I calculate the time cost. It is less than (4/3)*n.
Please point out if I have any mistake during the calculation.