Answer: Running time analysis

Question: In Quiz 3, we computed a parent array for a breadth-first search tree. Let's say we wrote the following code to compute the tree's depth.

int
nodeDepth(int which, int *parent) {
    if(parent[which] == -1) return 0;
    else return 1 + nodeDepth(parent[which], parent);
}

int
treeDepth(int *parent, int num_nodes) {
    int max_depth = -1;
    for(int i = 0; i < num_nodes; i++) {
        int i_depth = nodeDepth(i, parent);
        if(i_depth > max_depth) max_depth = i_depth;
    }
    return max_depth;
}

If num_nodes is n, what is the worst-case running time of the treeDepth()?

Answer: The running time of nodeDepth() is O(depth of which). Say the tree is basically a singly linked list. Then the amount of time consumed is 1+2+...+n=O(n^2).