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

This article covers advanced algorithm analysis topics such as divide and conquer, complexity, recurrence, and universal sink. It provides detailed explanations and examples for each topic, making it perfect for students and professionals. The article also includes references to Bankevich et al. (2012) and Pan (2012).

A A A T M A ADV NCED LGORI H N LYSIS
A t or ame ir t M a t mit Title and e ree[ u h N (s), F s . L s , O s D g s]
n tit tional A iliation[I s u ff (s)]

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.

Question 3
i) Every minor list that possesses a parameter of k takes Ɵ (k2).This will be the case of worst
incidences of time with the assistance of Insertion-Sort. The sorting process of n/k considers
n/k* Ɵ (k2) = Ɵ (nk) as worst-case of all the available time for similar minor cases.
ii)
 Ɵ(n) worst-case period is taken in connecting n/k sub lists to give n/2k minor lists
 Ɵ(n) worst-case period is taken in connecting n/2k sub lists to give n/4k minor lists
 Ɵ(n) worst-case duration is taken in connecting n/4k sub lists to give n/8k minor lists and
so on
 In general, connecting 2 minor lists into one list requires Ɵ(n) worst case duration
 In the incidence of using lg (n/k) connections, n/k can be connected and joined into one
list and this process would need Ɵ (n lg (n/k)) as its worst case duration.
iii)
In order to have Ɵ (nk+n lg (n/k)) =Ɵ (n lg n), any of the boundary conditions of n lg (n/k) =Ɵ
(n lg n) or nk=Ɵ (n lg n) must be achieved. As can be seen in the preceding two possibilities, it is
possible to conclude that the largest value of asymptotic k is Ɵ (lg n).
Question four
i)
T (n) = 3T (n/2) + n

In the case of such recurrence, a=3, b=2, f (n) =n and therefore what is obtained isnlogb a =nlog3 2,
considering that f (n) =Ω=(n¿ ¿ log3 2+ ϵ )¿ where ϵ =0.2,The application of case 3 will follow a
master theorem that it should be possible to correct the conditions of regularity that holds for for
f (n)
Having shown that the regularity condition is true, there is need to call for a proof of af(n/b)
≤ cf (n) for value of c<1 and all other subsequent values of n. Once it is possible to prove the
case, then it is possible to draw conclusion from T (n)=⊝( f ( n)) while applying case 3 of the
master theorem(Bankevich et al 2012).
Confirmation of the conditions.
af (n/b) =3(n/4)≤ cf ( n ) for c=0.7 and ≥ 2
It is therefore possible to conclude that the required solution is T (n) =⊝( f (n))=⊝( n).
ii)
A recurrence tree can be created for T (n) = 3T (n/2) + n, since the ceilings and the floors are
often not very necessary in the solution of recurrences,
The data in the table takes into assumption that n is an exact power of 2 .This is done for the
purposes of convenience to ensure that all the challenges of subunits sizes will be purely integers

Considering that the sizes of the sub problem are reducing by a factor of 2 every time there is a
one level reduction, which translates to a boundary condition of T(1). The determination of the
tree depth of size of the sub problem for a single node at a depth i is found to be n/2i . This
means that the sub problem will attain n=1 at the point n/2i=1 or its equivalent at the point i=lgn.
It is therefore possible that the tree will be having lgn+1 levels with the depths running from 0, 1,
2, 3…, lgn).
The stage that follows involves the determination of the cost at every level of the tree. The
number of nodes will be 3i at depth i since each of the levels is having thrice more nodes than the
preceding level. This is because there is a reduction by a factor of 2 for every level of the minor
problem starting from sizes down from the roots The determination of the cost of each of the
nodes at a depth i where i=0,1,2,3,…, lgn-1 is done using the equation 3i* n/2i=(3/2)in.The
determination at the lowest level when the depth is lgn, 3lgn=3lg3nodes.The contribution of each
node is T(1) for a total cost of nlg3 T(1) i.e. ⊝(nlg3) .The assumption made is that T(1) is a
constant.
In order get the cost of the whole tree, addition of other costs from different levels are done.

T ( n ) =n+ 3
2 n+( 3
2 )
2
n+( 3
2 )
3
n+…+ ( 3
2 )
lgn−1
n+⊝(nlg 3)
¿ ∑
k=0
lgn−1
(3
2 )
k
n+¿ ⊝(nlg3 )¿
=
( 3
2 )
lgn−1
3
2 −1
n+⊝(nlg3 )
=2 nlg 3−2 n+⊝( nlg3 )
=⊝( nlg3 )
iii)
In order to have a verification of the answer for all the available integers n, s.t≥ 1, the property P
(n),traces of similarity or match between the closed form of T (n)≤ dnlg 3−cn for particular values
of d and c s.t d>0 and c>0 are obtained. The results resemble the cases of T (n) = 3T (n/2) +
n(Pan 2012).
Question five
The i-th row if the adjacency will all be ‘0’should a vertex i be a universal sink as per the
definition. Also the i-th column will all be ‘1’apart from aii entry which clearly has similar
vertex. The description of algorithm is then done so as to determine the presence of a universal
sink.
The starting point is from aii, in case a current entry aij is be equal to ‘0’, this follows that j=j+1
(taking one step to the right), Also in cases of aij equal to 1then it implies i=i+1 (a single step

has been taken downwards). When that is done, there will be a stop at the last row at the entry
akn if not then at ank of the last column (n=|V|, 1≦ k ≦∨V ∨¿). The vertex k is verified if it
concurs with the definition of a universal sink. In case it meet the definition then the answer is
correct. If it does not meet the definition then there is no universal sink. In the absence of a
universal sink, the algorithm will therefore return no vertex. Also, the path starts at a11 will
finally come across the u-th row or u-th column with the presence of a universal sink u at
particular entry. Once it soon as it is on track, it is not possible to have it get off the track. It
will eventually stop at the correct point of entry.

REFERENCES
Bankevich, A., Nurk, S., Antipov, D., Gurevich, A. A., Dvorkin, M., Kulikov, A. S., ... &
Pyshkin, A. V. (2012). SPAdes: a new genome assembly algorithm and its applications to single-
cell sequencing. Journal of computational biology, 19(5), 455-477.
Pan, W. T. (2012). A new fruit fly optimization algorithm: taking the financial distress model as
an example. Knowledge-Based Systems, 26, 69-74.