How to prove that insert complexity in binary search tree is minimum O(log n)?
The minimal height of a BST is always log n, you can easily prove it by induction. Then if you want to insert a new node you need to find the corresponding leaf where to insert it, which takes at least log n operations (comparisons) in the worst case, more if the tree is not balanced (larger height). Hence you obtain an insert cost of O(log n). We always focus on the worst case scenario to compute the O-complexity.