-1
$\begingroup$

Some of my colleagues introduced some code into our codebase that was causing some serious performance issues. The feature they were implementing involved displaying data in a hierarchical fashion, but if there were more than 20 or so nodes involved, there was a serious delay (multiple seconds) before the user could see their data. And in one of our scenarios, we had around 50 or so nodes, and in that situation it ran for hours before completing.

I had no trouble replacing the code with something sane, that ran on the order of microseconds, but when explaining runtime complexity to the individuals who had created the code, I realized I wasn't sure how to determine the complexity of the algorithm in question.

In JavaScript, the code look something like this:

function DoUnspeakableEvil(root, nodes) {
    root.children = [];
    nodes.forEach(function (node) {
        if (node.parentId === root.id) {
            root.children.push(node);
        }
        node.children.forEach(node => DoUnspeakableEvil(node, nodes));
        node.children.sort(/* sort based on one of the fields */);
    });
}

In pseudocode:

Procedure Inefficient_Tree_Procedure:
    Given the tree's nodes and the root of the subtree
    For each node in the tree:
        If the node's parent id is the id of the subtree root:
            Add the node to the sub tree root's children
        If the root has children:
            For each child of the root:
                Run Inefficient_Tree_Proceedure on child
            Sort the children

Main
    Run Inefficient_Tree_Proceedure on the nodes with the tree's root (known ahead of time) as the root

Essentially, what's going on here is that we have an array of nodes, and we're given the member of that array which is the root of our 'tree'. Each node is able to identify its parent. This hierarchical data is usually about 3 levels deep, so on this first pass root.children gets populated with a sizable portion of the nodes. There is no sorcery here either: This poorly designed code runs completely synchronously, so every time it evaluates another node, it recurses on every found child up to that point. It also sorts all of the found children up to that point, each time it evaluates a node.

* Where I get lost *

Obviously, iterating over the nodes and finding the ones that are immediate children of the 'root' is a Ө(n) task. Sorting is likely going to be O(n log(n)) (depending on the browser on which we run this, since they all have different implementation strategies and some may use insertion sort for small arrays). Based on my understanding, if the sort and the recursive step weren't erroneously placed inside of the loop, and it did these steps once for each value of 'root', we would be looking at some sort of O(n log(n) log(n)) algorithm. The part that confuses me is the fact that they WERE in fact put in the loop, which means for each root, its going to recurse once a few times, recurse twice a few times, recurse three times a few times, etc... and then do the same with sorting. Sort an array of length 1 a few times, sort an array of length 2 a few times, etc....And repeat this complex process for each of the children it recurses on.

Basically, out of curiosity and for understanding's sake at this point, I'm looking to figure out and understand the runtime complexity of this, since my undergraduate education has clearly met its limits here.

$\endgroup$
  • 2
    $\begingroup$ Could you convert the code to pseudocode for those of us who don't speak Javascript? Also, did you check our reference question? $\endgroup$ – David Richerby Sep 7 '15 at 14:49
  • $\begingroup$ @DavidRicherby I will try to add some pseudocode. Also, I did look at the reference question, but it didn't seem to clear up for me that behavior of running the same code over an over on a growing set of children and how to analyze its complexity. $\endgroup$ – Dogs Sep 7 '15 at 15:03
  • $\begingroup$ I understand that you ask about complexity of this flawed procedure, but on top of it problem with runtimes is due to forEach function and probable scope traversing to find function provided to sort. forEach is not O(n). Another problem is that sort function goes up to three levels down, and since normal arrays are resizable it cannot be optimized. The pseudocode is doing what you think JS should do, unfortunately they don't. $\endgroup$ – Evil Sep 7 '15 at 16:08
  • $\begingroup$ @EvilJS In this case the sort function's strategy callback and this function are both declared on the prototype of the same object. I am also incredibly skeptical about the statement that forEach is not O(n). $\endgroup$ – Dogs Sep 7 '15 at 16:15
  • $\begingroup$ Traversing prototype chain is one thing, traversing closures and creating anonymous function is another. forEach casts variable to object and than it performs hasOwnProperty which (this time without prototype chaining) searches associative array for element. There is no guarantee that it is O(1), it can be tree with O(logn) search or worse. If object is boxed it is transformer to assembly, if prototypes come later, you encounter deoptimize. For the very same reason there is no indication to use hashtable. Try to explain approx 20 times slower forEach than for, growing with n. $\endgroup$ – Evil Sep 7 '15 at 16:28
1
$\begingroup$

So this is basically doing - For each node in the tree; go through all the other nodes in the tree, add into children, and sort children each time.

Yes, very inefficient.

If we have n nodes then the time should be

  • n - Each node in the tree
  • *n - go through all nodes in the tree
  • *(1 - add into children where relevant
  • +s log s) - sort, where s is the current node's size.

That last term $\sum_{i=1}^m i \log i$ comes to O($m^2 \log m$), so it depends on the shape of your tree. If the tree is very shallow (e.g., only the root is a non-leaf), this can therefore reach O($n^4 \log n$). If each node has up to m children, then it would be O($n^2 m^2 \log m$).

$\endgroup$
  • $\begingroup$ That last term was the one which confused me. As for the shape of the tree, about 1/2 to 2/3 of the tree are going to be leaf nodes in most situations, so that would explain why the execution time skyrocketed out of control as the number of nodes increased. Thanks for the help! I wanted to be able to explain thoroughly to the code authors why this algorithm worked fine in our local/dev environments, but suddenly became completely impractical when it reached our QA environment. $\endgroup$ – Dogs Sep 7 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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