Нетрудно заметитьГлубина дерева рекурсии равна <tex>\log_4 n = \frac{1}{2}\log_2 n</tex>Следовательно, что <tex>Q(n) = O(2^{\frac{1}{2}\log_2 n}) = O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемое.
}}
By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex> из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>.
