Question

1. explain what the worst case for the algorithm is

2.explain how you computed the time complexity

3.give the order of the time complexity of the algorithm

Code:

public class Degree {
    int degree; 
    public int maxDegree(Node node) {
        degree = 0; 
        if(node == null)
            return degree;
        findMaxDegree(node);
        return degree;
    }

     private void findMaxDegree(Node node) {
        if(node == null || node.numChildren() == 0)
            return;
        degree = Math.max(degree, node.numChildren());
        Node[] children = node.getChildren();
        for(int i=0; i<children.length; i++) {
            findMaxDegree(children[i]);
        }
    }
}

Answer 1

• The worst case for this algorithm is also the average case for it where we will travel through all the nodes in the tree.
  
• Explantion of how we computed the time complexity​​​​​​​
  • This piece of code does the following
    • For every node, it calculates its degree and updates the max degree variable if the new degree found is greater.
  • Since, we travel through all the node and all of its children in recursion, the time complexity for this will be the number of nodes in the tree.
• Hence the time complexity for this algorithm is Big-O( n ) where n is the number of nodes in the tree.

Example

say we have this tree with 10 nodes labeled 1 through 10

On executing the above function following will be the recursion flow

• maxDegree(1)

  • findMaxDegree(1)

    • findMaxDegree(2)

      • findMaxDegree(6)

    • findMaxDegree(3)

      • findMaxDegree(7)

      • findMaxDegree(8)

    • findMaxDegree(4)

      • findMaxDegree(9)

      • findMaxDegree(10)

    • findMaxDegree(5)

We can see that the function findMaxDegree was called with all the nodes once, Hence order is O(number of nodes)