Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink

[Author Name(s), First M. Last, Omit Titles and Degrees]

Question 1
For nI=0, nE=2nI+1=1
For nI=1, then nE=2nI+1=2+1=3
Assuming that the equation nE is true for k’<k, which means for any equation nI =k’<k, the
value of nE=2nI+1
Taking into consideration nI=k, nE=2(k-1) + (3-1). This means that the number of external nodes
is the same as the number of external nodes for a tree that has k-1 internal node + 3 (the addition
of internal nodes which have to have 3 children) subtract 1 (in generating the new internal node,
an external node was made into an internal node). Hence nE=2k-2+3=2k+1 (Ahuja, 2017)
Question 2
The algorithm makes use of the technique of divide-and-conquer. In the course of adoption of the
technique of divide-and-conquer, there will be a change in the lengths of both the sorted arrays T
and S. the length of T (or S) is denoted using len(T) (or len(S))at any given moment (Corke,
2017).
At any provided iteration, the median index of S is denoted using ms=len (S)/2 as well as the
medium of S by S[ms]. On the same note, the median index of T is denoted by mT=len (T)/2 as
well as the medium of T by T[mt]. a comparison can then be made between mt+ms and S[ms]
with T[mt] in the determination of which (right or left) half part of which of the arrays (S or T)
may be removed and then the smaller sub-problem be left for recursion (Evans, 2017)
The algorithm

Condition 1(ms+mt≥ k)
1.1 Condition 1.1 S[ms]≥ T [mt ]
The right bigger half of array S can be removed i.e. from S[ms] to its end and thereafter
recursively find the k-th smallest element in T and as well as the left smaller half of S
1.2 Condition 1.2 T[mt]¿ S[ms]
It is exactly symmetric with Condition 1.1, having T and S exchanged
Condition 2 (ms+mt<k):
2.1 Condition 2.1 S[ms]≥ T [ mt ]
The left smaller half of array T can be discarded and the recursively determine the (k-
mt)-th smallest element in S and in the right larger half of S (Rao & Yip, 2014)
2.2 Condition 2.2 T[mt]>S[ms]
This condition is exactly symmetric with Condition 1.1, having T and S exchanged
Time complexity:
At every iteration, half of some array is discarded and thus the time complexity is O (log (len(S))
+log (len (T))) which is O (logn) for the input arrays T and S of size n
Question 3
i) Each sub list that has a length of k takes Ɵ (k2) worst-case time with the aid of Insertion-Sort.
In order to sort n/k it takes n/k* Ɵ (k2) = Ɵ (nk) as worst-case time for such sub lists