Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink

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

Question 1
Suppose nI=1, then it means nE=2nI+1=2+1=3;
Suppose nI=0, then nE=2nI+1=1
Making a presumption that for k’<k, the equation nE holds, an equation provided in the form nI
=k’<k, the condition nE=2nI+1 is true.
Giving consideration to nI=k, then it follows that nE=2(k-1) + (3-1). This is interpreted as the
total external nodes is equivalent to the external nodes composed of k-1 nodes in addition to
3(the addition of 3 refers to the internal nodes that have 3 children) removing 1 (this is a
replacement of the external node that was changed into an internal node when creating a new
internal node). An inference can thus be reached at that nE=2k-2+3=2k+1
Question 2
The algorithm adopts the divide-and-conquer technique. While adopting this divide-and-conquer
technique, an alternation in the lengths of the two sorted arrays T and S is notice. Len (T) is used
in the denotation of the length of T while the length of S is denoted using len (S) at any provided
time.
Any certain iteration given, ms=lens (S)/2 is used in the denotation of the medium index of S
besides medium of S by S[ms]. On a similar note, mT=len (T)/ 2 is used in the denotation of the
medium index of T alongside as the medium of T is denoted by T[mt]. mt+ms and S[ms] can
then be compared against T[mt] that aids in finding the half part i.e. right or left of the arrays i.e.
S or T that may be eliminated or discarded to leave the smaller sub-problems for recursion.
The algorithm

1st Condition (ms+mt≥ k)
Condition 1.1 when S[ms]≥ T [mt ]
Discarding of the right larger half of array S may be performed that would mean removal from
S[ms] from the end and thereafter recursive determination of the k-th smallest element that is in
T alongside the left smaller half of S
Condition 1.2 when T[mt]¿ S[ms]
Under this condition, a direct and exact symmetry with condition 1.1 with the arrays T and S
exchanged is noticed
Condition 2 (ms+mt<k):
Condition 2.1 S[ms]≥ T [ mt ]
This condition encompasses the discarding of the left smaller half of T array and then finding the
(k-mt)-th of the smallest element in S alongside in the right large half of array S
Condition 2.2 T[mt]>S[ms]
Similar Condition 1.2, Condition 2.2 has exhibits the exact symmetry with condition 1.1, with
the arrays T and S exchanged
Time complexity: At a specific iteration, discarding of half of some array occurs and thereby the
time complexity becomes O (log (len(S)) +log (len (T))) which can be simplified to O (logn) at
size n as the input of the arrays T and S
Question 3