Data Structures and AlgorithmsKey to Homework Assignment 61. For each of the following code segments, find a function f (n) with the property that thenumber of statements executed by the segment is O(f (n)). Your functions f(n) should be assimple as possible.(a) sum = 0;for (int i = 0; i < n; i++)sum++;f(n) = n.(b) sum = 0;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)sum++;The inner loop is Θ(n). So f(n) = n2.(c) sum = 0;for (int i = 0; i < n; i++)for (int j = 0; j < n*n; j++)sum++;The inner loop is Θ(n2). So f (n) = n3.(d) sum = 0;for (int i = 0; i < n; i++)for (int j = 0; j < i; j++)sum++;The inner loop is Θ(i). So the entire code segment has runtime proportional ton−1Xi=0i =n(n − 1)2,and f(n) = n2.(e) sum = 0;for (int i = 0; i < n; i++)for (int j = 0; j < i*i; j++)for (int k = 0; k < j; k++)sum++;1Data Structures and Algorithms, Key to Homework 6 2The innermost loop is Θ(j). So the for j loop isΘi2−1Xj=0j= Θ i2(i2− 1)2!,which is the same as Θ(i4). So by the fact thatnXt=1tkis O(tk+1),we can conclude that f(n) = n5.(f) sum = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= i*i; j++)if (j % i == 0)for (int k = 0; k < j; k++)sum++;The innermost loop will only be executed when j is is a multiple of i, which will occurprecisely i times. The remaining passes through the for j loop will simply execute thetest and increment j. So we can rewrite the code so that it has the same runtime (up tobig-Θ) as follows.sum = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++) {j_prime = i*j;for (int k = 0; k < j_prime; k++)sum++;Code that has runtime i-1;}The runtime of the body of the for j loop is Θ(i + j prime) = Θ(i+ij). So the runtimeof the for j loop isΘiXj=1(i + ij)= Θ i2+i2(i + 1)2!,which is Θ(i3). So by the result on sums of powers of i, we see that f(n) = n4.2. Problem 5.2, page 161. Define the degree of a node as the number of its nonempty children.Prove by induction that the number of degree 2 nodes in any binary tree is one less than thenumber of leaves. (You can assume that the tree is nonempty.)We use induction on n, the number of nodes in the binary tree. If T is any binary tree,we use the notation l(T ) and d(T ) to denote the number of leaves of T and the number ofdegree 2 nodes of T, respectively. So we wish to show that for any nonempty binary tree Tl(T ) = d(T ) + 1.Data Structures and Algorithms, Key to Homework 6 3Base case. If T is a binary tree with 1 node, then T consists of a single leaf, and no othernodes. In particular, it has no degree 2 nodes. So in this case l(T ) = d(T ) + 1.Induction hypothesis. Suppose then that n0is a positive integer with the property that if Tis any binary tree with n = n0(≥ 1) nodes, then l(T ) = d(T ) + 1.Induction step. Suppose now that T is a binary tree with n = n0+ 1 ≥ 2 nodes. Then (aswe saw in class) T has a leaf L. By deleting L from T, we get a new tree T0with n = n0≥ 1nodes. So by the induction hypothesis, l(T0) = d(T0) + 1. We consider two cases:(a) L has no sibling in T, and(b) L has a sibling in T.Note that since T has at least two nodes, L is not the root of T, and hence L has a parentP in T. In case (a), P has degree 1 in T, and hence it’s a leaf of T0. Thus, l(T ) = l(T0) andd(T ) = d(T0). So in this case, we have l(T ) = d(T ) + 1.In case (b), P has degree 2 in T, and hence degree 1 in T0. Thus l(T ) = l(T0) + 1 andd(T ) = d(T0) + 1. So by the induction hypothesis, we have thatl(T ) = l(T0) + 1 = d (T0) + 1 + 1 = d(T ) + 1.3. Problem 5.5, page 162. Write a function named search that takes as input a binary tree (nota BST!) and a value K, and returns true if value K appears in the tree and false otherwise.Your function should have the following prototype.boolean search(BinNode rt, int K)private boolean search(BinNode currNode, int key) {if (currNode == null)return false;Elem currElem = (Elem) currNode.element();if (currElem.key() == key)return true;boolean hasKey = search(currNode.left(), key);if (hasKey)return true;elsereturn search(currNode.right(), key);} // search4. Problem 5.7, page 162. Define the internal path length for a tree as the sum of the depths ofall internal nodes, while the external path length is the sum of the depths of all the leaves.Prove by induction that if T is a full binary tree with n internal nodes, I is T ’s internal pathlength, and E is T ’s external path length, then E = I + 2n for all n ≥ 0.We use induction on n, the number of internal nodes in the binary tree. If T is any binarytree, we use the notation I(T ) and E(T ) to denote the internal and external path lengths ofT, respectively.Data Structures and Algorithms, Key to Homework 6 4Base case. If a binary tree T has no internal nodes, it can either be empty, or it can havea single node, the root. In either case, E(T ) = I(T ) = 0, and we see that for this caseE(T ) = I(T ) + 2n.Induction hypothesis. Suppose then that n0is a nonegative integer with the property that anyfull binary tree T with n = n0(≥ 0) internal nodes satisfies the formula E(T ) = I(T ) + 2n.Induction step. Suppose now that T is a full binary tree with n = n0+ 1 ≥ 1 internal nodes.As discussed in class, T contains at least one internal node P, both of whose children, L andL0, are leaves. Consider the tree T0obtained from T by deleting L and L0from T. Then, inT0the node P is a leaf. So T0contains n = n0internal nodes. Furthermore, if Q is any nodeof T0different from P, the children of Q in T0are the same as the children of Q in T. HenceT0is full, and we can apply the induction hypothesis to conclude that E(T0) = I(T0) + 2n0.If d(Q) denotes the depth of a node of T, we know that d(L) = d(L0) = d(P ) + 1. Thus, wehave thatE(T ) = E(T0) − d(P ) + 2d(L) andI(T ) = I(T0) + d(P ).So we have thatE(T ) = I(T0) + 2n0− d(P ) + 2d(L)= I(T ) − d(P ) + 2n0− d(P ) + 2d(L)= I(T ) + 2n0− 2d(P ) + 2d(P ) + 2= I(T ) + 2(n0+