# Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink

8 Pages1956 Words422 Views

This article covers the techniques of divide and conquer, recurrence, and universal sink in advance algorithms. It explains the time complexity and proofs of regularity conditions. It also provides insights into insertion-sort and merging sublists. The article cites various authors and their works on the subject.

## Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink

BookmarkShareRelated Documents
[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

## End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
|9
|1953
|138

|8
|1712
|254

|9
|2086
|492

|9
|2127
|207

|8
|2224
|310

|11
|2061
|1060

### Support

#### +1 306 205-2269

Chat with our experts. we are online and ready to help.