What is the computational complexity of this problematic code we had

Question

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.

Answer 1

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