Advanced Algorithm Analysis - Desklib

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

Question 1
If nI=1, then it follows that nE=2nI+1=2+1=3;
When nI=0, nE=2nI+1=1
Assuming for k’<k, the equation nE is true, it would mean that an equation given in the form nI
=k’<k, the condition nE=2nI+1 holds.
Looking at nI=k, then nE=2(k-1) + (3-1). This is translated as the total external nodes is equal to
the tree external nodes composed of k-1 nodes in addition to 3(the addition of 3 is in references
to the internal nodes that have 3 children) removing 1 (this is compensation of the eternal node
that was converted into an internal node at the time of generation of a new internal node). It can
thus be concluded that nE=2k-2+3=2k+1
Question 2
The divide-and-rule conquer method is adversely used by the algorithm. In the process of the use
of this method, deviations are noticed in the lengths of the two sorted arrays S and T in which len
(T) is used to represent T while the lens (S) is used in the representation of the array S at a
particular time.
At a given iteration, medium index of S is represented by ms=len (S)/2 and that of the medium of
S denoted by S[ms]. Conversely, the medium of T is represented using T[mt] even as the
medium index of T is denoted using mT=len (T)/2. T[mt] can be compared with mt+ms and
S[ms] that will aid in the calculation of the half part (left or right) of which of the two arrays, S
or T, may need to be discarded to allow for recursion of the smaller sub-problem (Poursina,
2016).

Condition 1(ms+mt≥ k)
Condition 1.1 S[ms]≥ T [mt ]
Elimination of the right larger half of array S may be performed where it is removed from S[ms]
to the last and hence determining the k-th smallest elements that is in T recursively alongside the
left smaller half of array S
1.2 Condition 1.2 T[mt]¿ S[ms]
This condition has the same symmetry as that of condition one with the main and only difference
being witnessed in the exchange of T and S
Condition 2 (ms+mt<k):
2.1 Condition 2.1 S[ms]≥ T [ mt ]
Contrary to condition 1, this condition could involve the removal of the left smaller of T and
thereby proceeding to calculate the (k-mt)-th smallest element in array S recursively alongside in
the right greater half of array S
2.2 Condition 2.2 T[mt]>S[ms]
This condition has the same symmetry as that of condition one with the main and only difference
being witnessed in the exchange of T and S
Complexity in time: At each of the iterations, to the tune of 50% of a certain array is removed,
making the time complexity to be O (log (len(S)) +log (len (T))) which when simplified remains
O (logn) for size n inputs of the T and S arrays