2
$\begingroup$

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)$

My solution:

  • 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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ $\log n + \log\log n$ is $O(\log n)$ but not $O(\log\log n)$ so, without any further checking, your analysis seems to be flawed. $\endgroup$
    – David Richerby
    Jun 17, 2015 at 10:16
  • $\begingroup$ right..I just paid attention to that. But how could I get past that? $\endgroup$
    – ThunderWiring
    Jun 17, 2015 at 11:33
  • $\begingroup$ First you should correct the $O(\log(n) + \log\log n) = O(\log\log n)$ into ...$=O(\log n)$, as suggested by @D since it is painful to read. Then, your step 2 does seem incorrect. You have $n$ small AVL trees, each insertion is bound by $\log\log n$ cost since they have each at most $log n$ size, but you have $\log n$ nodes to insert in each, which makes a total cost $O(n\log n\log\log n)$ ... BTW, what is your definition of median value. $\endgroup$
    – babou
    Jun 17, 2015 at 14:13
  • $\begingroup$ a median is: ceiling((n+1)/2) element in size $\endgroup$
    – ThunderWiring
    Jun 17, 2015 at 15:02

2 Answers 2

Reset to default
3
$\begingroup$

Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The way I thought about it is as follows: since each node belongs to a small AVL, and it took $O(\log\log n)$ to insert it there(to the small AVL), thus, since we got $n$ nodes, it should take $O(n\log\log n)$. where is my mistake here? $\endgroup$
    – ThunderWiring
    Jun 17, 2015 at 16:02
  • $\begingroup$ What I understand from your construction is that each node is inserted in several small AVL trees, $\endgroup$
    – babou
    Jun 17, 2015 at 16:07
  • $\begingroup$ that's correct. $\endgroup$
    – ThunderWiring
    Jun 17, 2015 at 16:11
  • $\begingroup$ @ThunderWiring Is it correct that you build $n$ small AVL. Is it correct that each contain on the order of $\log n$ nodes (You say so yourself). So that makes $0(n\log n)$ nodes to insert, each in $O(\log\log n)$ steps. Hence the answer I gave you. I do not see what is still a problem. ... but though I did not work it out in detail, I would not try to solve your problem the way you do it. $\endgroup$
    – babou
    Jun 17, 2015 at 19:27
1
$\begingroup$

Maintaining one AVL tree for the whole process is enough, and more efficient.

  • Setup another AVL tree T, initially empty.
  • Perform DFS on original AVL tree
    • Insert node to T on entering the node,
    • Delete node from T on leaving the node.
    • Find and record the median after inserting each node.

In the DFS process, T actively maintains all nodes along the path from root to current node, similar to the stack (explicitly or implicitly) maintained in DFS.

The size of T is $O(\log n)$ during the whole process, so each insertion/deletion/query cost $O(\log \log n)$. And each node in original AVL is inserted/deleted/queried exactly once. So the overall complexity is $O(n \log \log n)$.

The maintained AVL tree T can be replaced by other running median data structures. A common data structure min heap + max heap, maintaining the 2 halves partitioned by current median, which can report current median in $O(1)$. (insertion/deletion is still $O(\log n)$)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. Read questions carefully before answering. This question is not about a better algorithm but about the asymptotic cost of the solution presented in the question. Some users might downvote for that. But you do give the answer the original poster was looking for, though he did not ask it. $\endgroup$
    – babou
    Aug 11, 2015 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.