Which of the following statements are true? Let $T(n)$ denote the time complexity of performing insertion in an n-element Binary Search Tree.