A search operation in B-Tree can be O(logn) because we can perform a binary search on the key we are looking for at any node. When inserting a key in a B-Tree node which isn't full and is the leaf node, we would need to scan all the elements of the node to make an insertion in the sorted order, so the worst case time complexity would be O(2d-1) where d = Degree of the B-Tree.
Example:
B-Tree degree = 3 Max Items = 2(3) - 1
If my B-Tree has just a root node which isn't full then inserting a value 98 in the below node will require me to shift all my keys one slot to the right to maintain the sort order, which means I would need to go through all my keys to insert the key at the right position making it O ( 2d - 1 ), where d = degree of B-Tree.
| 99 | 100 | 101 | 102 | NULL |
After insertion
| 98 | 99 | 100 | 101 | 102 |
I would like to understand how the insert operation has a time complexity of O ( log n ).
The "scan all the elements of the node", you are tell us, is O(2d-1) i.e. constant time. In the worst case you also have to split a node which is O(k). You do that for each node from the root to leaf which is at most O(log n) nodes. O(2d -1 ) * O(k2) * O(log n) = O(log n).