Since the height of an AVL tree is O(log n), the time complexity of the **search**, **insert**, and **delete** methods in **AVLTree** is O(log n). The time complexity of the **search**, **insert**, and **delete** methods in **AVLTree** depends on the height of the tree. We can prove that the height of the tree is O(log n).

Let G(h) denote the minimum number of the nodes in an AVL tree with height h. Obviously, G(1) is 1 and G(2) is 2. The minimum number of nodes in an AVL tree with height h >= 3 must have two minimum subtrees: one with height h - 1 and the other with height h - 2. Thus,

`G(h) = G(h - 1) + G(h - 2) + 1`

Recall that a Fibonacci number at index i can be described using the recurrence relation F(i) = F(i - 1) + F(i - 2). Therefore, the function G(h) is essentially the same as F(i). It can be proven that

`h < 1.4405 log(n + 2) - 1.3277`

where n is the number of nodes in the tree. Hence, the height of an AVL tree is O(log n).

The **search**, **insert**, and **delete** methods involve only the nodes along a path in the tree. The **updateHeight** and **balanceFactor** methods are executed in a constant time for each node in the path. The **balancePath** method is executed in a constant time for a node in the path. Thus, the time complexity for the **search**, **insert**, and **delete** methods is O(log n).

## Top comments (0)