Time Complexity of Split AVL Tree Function

Question

I have the following code for splitting the AVL tree and I'm not quite sure if it has Time Complexity of O(log(n)) or O((log n)²).

Note:

• The Complexity of join is O(log(n)) where n is the Number of Elements in Two Trees combined
• Complexity of insert is also O(log(n)) where n is the Number of Elements in the Tree.

    node* split(node* t, int k)
    {  

        if (t==NULL) 
        {
            return new_node(0);
        }

        if(t->val == k) {
           node* temp = new_node(0);
           temp->left=t->left;
           temp->right=t->right;

           temp->height = max(height(temp->left), height(temp->right)) +1;
           printf("%d TEMP\n", t->val);
           display(temp);
           return temp;    
       }
       if(k < t->val) {
           node* temp = split(t->left, k);
           temp->right = join(temp->right, t->right);
           temp->right = insert(temp->right, t->val);
           return temp;
       }
       if(k > t->val) {
           node* temp = split(t->right,k);
           printf("t->left\n");
           node* blah1, *blah2;
           blah1 = t->left;
           blah2 = temp->left;
           temp->left = join(blah1, blah2);
           temp->left = insert(temp->left, t->val);
           return temp;
        }
    }

Answer 1

It should have O(log (n)^2) worst time complexity, since in the worst-case you'll be calling split lg n (i.e. on each depth) and your function takes O(log n) to call join at each depth, log n * O(log n) = O(log (n)^2)