Here, \(n\rightarrow\infty\), therefore the maximum levels become \(i\ =\ 2\log_{\frac{9}{4}}n\)
Total time taken by the function can be expressed as sum of time taken at each level. Therefore,
\(T\left(n\right)=cn^2+\frac{5}{9}cn^2+\frac{5^2}{9^2}cn^2+.\ .\ .\ \left(\frac{5}{9}\right)^icn^2\)
\(=cn^2\left(1+\frac{5}{9}+\frac{5^2}{9^2}+.\ .\ .\right)\ \left[a=1;\ r=\frac{5}{9}\right]\)
\(=cn^2\left(\frac{1}{1-\frac{5}{9}}\right)\ \Rightarrow\frac{9}{4}cn^2\ \left[n\rightarrow\infty\ so\ we\ use\ G.P\ Formula\ as\ \frac{a}{1-r}\right]\)
Thus, \(T\left(n\right)\ =\ O\left(n^2\right)\)
Also if we consider the extreme left of the tree which reaches the boundary condition fastest, gives us \(T\left(n\right)=\Omega\left(dn^2\right)\)
Thus we can say \(T\left(n\right)\ =\ \theta\left(n^2\right)\)
2.a) There are total K-Queues of n passengers per queue, filled to their maximum capacity.
Let 'ar' be the array representing the given scenario. So the array dimensions would become ar[k][n]
Suppose we have a procedure 'Single-Queue(ar[k][n], A, m, 0)'
Single-Queue(ar[k][n], A, k, i){
1 if i < k then
c1(n + 2n + 3n.... + kn) B = merge (ar[i], A)
1 return Single-Queue ( ar, B, k, i+1 )
else
1 return A
so we can calculate the total time taken by the algorithm by assuming each step takes the time shown before it.
\(\ c_1\left(n\ +2n+3n+.\ .\ .+kn\right)\ +k+1\ +k+1\)
\(\left(c_1n\left(1+2+3+.\ .\ .\ +k\right)\ \right)+2\left(k+1\right)\)
\(\left(c_1n\left(\frac{k\left(k+1\right)}{2}\right)+2\left(k+1\right)\right)\)
\(\frac{c_1n\left(k^2+k\right)}{2}+2k+2\)\(\)
\(\left(c_1nk^2+c_1nk+4k+4\right)\)
2.b) We could use merge sort technique to merge the elements in the single array and then apply merge sort on the array with size kn
but that would give us the complexity of \(O\left(kn\log kn\right)\)
- So, we need to vertically divide the K- sub arrays.
- Then find the minimum element in the vertical split and place it in the array with size \(kn\)
- Keep getting the minimum from each vertical split and place it in the array until all of the elements are placed in the array.
- Since we divide the array such that only K elements are processed at once this gives us the \(\log k\ divisions\)
- Placing the kn elements would require at max kn time, thus the complexity of the algorithm becomes \(O\left(kn\log k\right)\)
3. a)
1. Assuming the intervals are provided in the form of a 2-D array where \(ar\left[i\right]\left[0\right]=s_i\ AND\ ar\left[i\right]\left[1\right]=t_i\ \).
2. Now, Using Merge-Sort sort the elements on the basis of \(s_i\): \(s_i<s_{i+1}\)
3. Now, \(for\ i\leftarrow0\ to\ ar.length-1\ do\):
\(if\ \ i+1\le ar.length-1\ AND\ ar\left[i\right]\left[1\right]>ar\left[i+1\right]\left[0\right]\ then\)
return True
\(else:\)
\(i\leftarrow i+1\)
return False
OR
- For the third step we can again apply divide and conquer approach.
- After sorting , we use this procedure, initially l=0, r = ar.length, f = array of size ar.length
- This will be done in \(O\left(\lg n\right)\)
INTERVAL-CHECK(A, l,r, f){
\(if\ l<r\ then:\)
\(m=\frac{\left(l+r\right)}{2}\)
\(if\ A\left[m\right]\left[1\right]>A\left[m+1\right]\left[0\right]\ then:\)
\(f\left[m\right]\ =\ 1\)
\(else\ then:\)
INTERVAL-CHECK(A, l, m, f)
INTERVAL-CHECK(A, m+1, r, f)
- Now iterate over f to see if there's any 1 in the array which will be done in \(O\left(n\right)\ \left[n\leftarrow\ ar.length\right]\)
b) Assuming our algorithm returns true if at least one interval overlaps and returns false if none overlap.
1. When \(n=1\), such that only 1 interval is given it works as it does not overlap with any other interval
2. When \(n=2\), there are two cases,
a) the intervals overlap
b) the intervals don't overlap
a) if the intervals overlap, for e.g. ar = {{4,9},{3,7}}
\(\implies\)First we sort the given array such that \(s_i<s_{i+1}\) , the array now becomes {{3,7},{4,9}}
\(\implies\)Now we iterate from \(i=0\) to \(ar.length-1\) i.e from 0 to 1
it checks for the condition, since it is true it will return true
b) if the intervals don't overlap, for e.g. ar = {{5,9}, {11, 26}}
\(\Rightarrow\) First we sort the given array, in this case its already sorted,
so our array after sorting is the same as the given array.
\(\Rightarrow\) Now we iterate from \(i=0\) to \(ar.length-1\) i.e from 0 to 1
it checks for the condition, since it is false it will return false
3. For \(n=n+1\), Again there are two possible cases,
a) the intervals overlap
b) the intervals don't overlap
a) so for the first n intervals our algorithm works correctly, the \(\left(n+1\right)^{th\ }element\ will\ be\ compared\ with\ \left(\left(n+1\right)\ -1\right)^{th}\ element,\ i.e\ n^{th}\)
This is similar to comparing two intervals as in the above case so it will return true which is the correct result
b) If the intervals do not overlap,our algorithm runs correctly for the first n intervals,
so it will compare \(n^{th}\ interval\ with\ n+1^{th}\ interval\) which is similar to the above case
Thus it returns false which is the correct result .
c) We begin by sorting the given intervals which occurs in \(O\left(n\log n\right)\)
in the next step we iterate over n elements checking for the given elements which happens n times.
Thus our algorithm takes \(O\left(n\log n\right)\ time\)
4 a. The outer loop that decides the size of the window increments by a factor of 2.
So at \(i^{th}\) Iteration when the window size reaches the size of the given array,
\(\Rightarrow\ 2^i=n\) (Assuming the size of the array is a power of 2)
\(\Rightarrow i\ =\ \log_2n\)
So time taken to merge two sub arrays that are sorted takes \(\frac{n}{2}+\frac{n}{2}=n\ time\)
So we merge total of \(i\ \) times, the maximum time taken by the algorithm would become,
\(\Rightarrow O\left(n\log_2n\right)\)
b. Advantage: The recursive implementation involves calling the stack for bookkeeping purposes which creates a lot of overhead. So it makes the bottom-up approach faster than top-down approach.
Disadvantage: Complex to implement.