Advanced Algorithm Analysis: Techniques, Complexity, Recurrence, and Universal Sink

Question one
In the cases of first example when nI=0, nE=2nI+1=1
Also when nI=1, then nE=2nI+1=2+1=3
Taking that the provided equation of nE is applicable for K’<k,then for every equation of nI
=k’<k, corresponding value of nE will be given as nE=2nI+1. Also considering that nI=k,
nE=2(k-1) + (3-1),the overall number of the nodes on the external point will be equal to the
number of nodes for the tree that possesK-1 and internal node+3.This is the same as the addition
of the internal nodes that are supposed to have 3 children. In order to get the new internal node,
subtraction of 1 is done. This will subsequently make external node into internal node. Therefore
nE=2k-2+3=2k+1.
Question 2
The technique that is used in the algorithm is called divide and conquer. In the process of the
application or use of this technique of divide and conquer, the sorted arrays of T and S changes
their lengths.The denotation of lengths is as follows. len(T) (or len(S)) and also T (or S) at any
point of application. In every point of use, the medium of S is represented as ms=len (S)/2 and
for S is obtain as S[ms].Similarly mT=len (T)/2 is used for the denotation of the median index
for T.This is done alongside use of T by T[mt].In the process of determining which part is better
between mt+ms and S[ms] with T[mt],a comparison is required. This comparison will
concentrate on the half part of the available arrays of T or S which will be removed and recursion
done on the smaller sub-problems.
The algorithm

The algorithm
Boundaries that are available here will entail 1(ms+mt≥ k)
1.1 Case 1.1 S[ms]≥ T [mt ]
The bigger half of the S array can be effectively eliminated from S[ms] to the other end
This will provide effective room for getting smaller half of K-t.This will completely define
element in T as well as the remaining half of S .
1.2 Case1.2 T[mt]¿ S[ms]
It is exactly a reflection of the Case1.1, having T and S with reversed positions.
Case 2 (ms+mt<k):
2.1 Case 2.1 S[ms]≥ T [ mt ]
In order to recursively determine the (k-mt)-th smallest element in S.the left half of array
T must be eliminated. Also the right larger half of S must be removed.
2.2 Case 2.2 T[mt]>S[ms]
This case is exactly a reflection of Case 1.1, having T and S reversed.
Complexity of time:
Half of some arrays is normally eliminated at every point of iteration and this make the
complexity of time to be O (log (len(S)) +log (len (T))) that translates to O (logn).This
will be applicable for every input for arrays S and T in the size of n.