I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness")
Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree has the parameter $w_i$ (which is an integer)
The task: To make an algorithm which returns an array of size $n$ such that in the cell $i$ there is the median value of all the $w_i$ of all the nodes from the root of the AVL to the node $i$.
Running time: $O(n\log\log n)$
- For each node among the $n$ nodes in the AVL, I build a separate AVL containing the $O(\log n)$ nodes(because the depth of each node is $O(\log n)$) on the path to it from the root.
- Each insertion to an AVL takes $O(\log n)$ ($n$ = number of nodes), but number of nodes here is $O(\log n)$, therefore, each insertion takes $O(\log\log n)$, and since there are $n$ nodes, then building the $n$ AVLs takes $O(n\log\log n)$
- Finding the median for each AVL takes $O(\log n)$ (using Select) since there are $O(\log n)$ values in the tree. Then, we put in the output array at the cell $i$ the median value which we just found.
Thus, building each AVL and finding the median, is done in $O(\log(n) + \log\log n) = O(\log n)$.
My Question: I'm uncertain about step 2 in the described algorithm above: does building the $n$ AVL trees takes actually $O(n\log\log n)$ running time?