(i) With the help of an example, briefly explain the dominant term in complexity.
The dominant term is the term in the complexity expression that grows the fastest as the input size N increases.
Suppose we have an algorithm with a time complexity given by the function T(N) = 3N2 + 5N + 7. As N becomes very large, 3N2 will grow much faster than other terms in the function. Therefore, 3N2 is the dominant term.
(ii) Answer the following questions based on the diagram of a binary tree given below:
(a) Name the external nodes of the tree.
External nodes are the leaf nodes. They do not have any children. So, F, I, C, G are external nodes.
(b) State the degree of node M and node L.
Degree refers to the number of children of a given node. The degree of M is 2 and the degree of L is 1.
(c) Write the post-order traversal of the above tree structure.
F→I→M→E→C→L→G→H→A