Какова временная сложность этого алгоритма самого низкого общего предка?

Question

Я только что написал это, но я думаю, что это довольно медленная реализация.Я не заинтересован в том, чтобы кто-то предоставлял более быстрый алгоритм;Я хочу знать временную сложность этого алгоритма (и почему).

   class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }   

            boolean leftContainsP = contains(root.left, p); 
            boolean leftContainsQ = contains(root.left, q);

            if (leftContainsP && leftContainsQ) {
                return lowestCommonAncestor(root.left, p, q);
            }

            boolean rightContainsP = contains(root.right, p); 
            boolean rightContainsQ = contains(root.right, q);

            if (rightContainsP && rightContainsQ) {
                return lowestCommonAncestor(root.right, p, q);
            }   

            return root;
        }

        public boolean contains(TreeNode root, TreeNode node) {
            if (root == null) {
                return false;
            } 

            if (root == node) {
                return true;
            }

            return contains(root.left, node) || contains(root.right, node);
        }  
    }

Вот моя мысль:

Для каждой итерации lowerCommonAncestor, я вызываю "содержит" 4 раза.Содержит прогоны в O (p), где p - количество узлов в дереве.

Но я всегда называю содержит в дереве половину размера ввода.

Кроме того,функция lowerCommonAncestor повторяет logN раз (поскольку она всегда вызывает дочерний элемент).

Таким образом, моя сложность такова:

(N + N / 2 + N / 4 + N / 8 ...) * 4

= O (N)

Но я не думаю, что это на самом деле так быстро, интуитивно, поскольку повторяет много работы.