Ask a question from expert

Ask now

Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink

8 Pages1956 Words422 Views
   

Added on  2023-06-05

About This Document

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

   Added on 2023-06-05

BookmarkShareRelated Documents
[Author Name(s), First M. Last, Omit Titles and Degrees]
Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink_1
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
Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink_2
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
Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink_3

End of preview

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

Related Documents
Advanced Algorithm Analysis: Techniques, Complexity, Recurrence, and Universal Sink
|9
|1953
|138

Advanced Algorithm Analysis - Desklib
|8
|1712
|254

Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink
|9
|2086
|492

Advanced Algorithm Analysis - Desklib
|9
|2127
|207

Algorithms: Internal Node Children, Kth Smallest Key, Sorting, Recurrence, Adjacency Matrix
|8
|2224
|310

Assignment On Design and Analysis of Algorithms
|11
|2061
|1060