Problem Detail: B-tree is a data structure, which looks like this: 
If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc. The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node. Then, we must go through all the levels of the structure, and they’re $log_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case. Putting these information together, we should have $O(n) * O(log n) = O(n * log n)$ complexity. But the complexity is just $O(log n)$ – why? What am I doing wrong?
If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc. The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node. Then, we must go through all the levels of the structure, and they’re $log_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case. Putting these information together, we should have $O(n) * O(log n) = O(n * log n)$ complexity. But the complexity is just $O(log n)$ – why? What am I doing wrong?
Asked By : Eenoku
Answered By : Evil
You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$. There height will be in the best case $lceil log_m(N + 1) rceil$, and the worst case is height $lceil log_{frac{m}{2}}(N)rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by constant.
Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log_2(m)$, so the proper complexity is $O(log(N) * log(m))$.
Since the $m << N$ and what is more important it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).
The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by constant.
Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log_2(m)$, so the proper complexity is $O(log(N) * log(m))$.
Since the $m << N$ and what is more important it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/59453 3.2K people like this
