Theory Assignment-1: ADA Winter-2024

Sushant Kumar (2022520) Syamantak Paliwal (2022529)

1 Preprocessing
We assign k-1 to k after taking k as input. This caters to our assumption that there is 0 indexing.

2 Algorithm Description
Motivation : When we try to find time complexity smaller than O(n), we immediately consider this question,
can the problem be solved in logarithmic time. Being given sorted arrays, when we consider a logarithmic time
search, binary search seems to be the most suitable candidate.
Algorithm :
We have three sorted arrays A, B, C. we have to find k th minimum element. Let a, b, c be the indices of the
median elements of A, B and C respectively.
1. We check if two of the arrays are empty. In this case, k th element is X[k] where X is the non-empty array.
This also serves as the base case for our recursion.
2. We find the middle elements of the sorted arrays(A[a], B[b], C[c]).
3. If k is greater than (a + b + c), then we discard the left half of array(including the median element) which
has minimum element out of A[a], B[b] and C[c]. We now recursively find (k − a − 1)th minimum element out
of remaining arrays. If k is less than or equal to (a + b + c) we discard the right half of the array(including
the median element) with maximum element out of A[a], B[b] and C[c]. We now recursively find k th minimum
element out of remaining arrays.

3 Recurrence Relation
Here f = findKMin

f (A, B, C, k) = {

A[k] if B = ϕ, C = ϕ
B[k] if C = ϕ, A = ϕ
C[k] if A = ϕ, B = ϕ

f (A[a + 1 :], B, C, k − a − 1) if k > a + b + c and A[a] is min(A[a], B[b], C[c])

f (A, B[b + 1 :], C, k − b − 1) if k > a + b + c and B[b] is min(A[a], B[b], C[c])
f (A, B, C[c + 1 :], k − c − 1) if k > a + b + c and C[c] is min(A[a], B[b], C[c])

f (A, B, C[: c], k) if k <= a + b + c and C[c] is max(A[a], B[b], C[c])

f (A[: a], B, C, k) if k <= a + b + c and A[a] is the max(A[a], B[b], C[c])
f (A, B[: b], C, k) if k <= a + b + c and B[b] is the max(A[a], B[b], C[c])
}

4 Complexity Analysis
Time Complexity :
We claim that our time complexity is O(log n). We will prove it by the substitution method.

1
 Notation : T() is the function computing number of steps taken by function to complete. log
is the natural logarithm(base e).
P
Let T (f indKmin(A, B, C, k)) < c ∗ log( cyc len(A)) for some c > 1 ∀ findKmin(A’, B’, C’, k’) where
len(A′ ) + len(B ′ ) + len(C ′ ) < 3n and k < len(A′ ) + len(B ′ ) + len(C ′ ).
Base Cases :
T (f indKmin(A, ϕ, ϕ)) = c1 for some constant c1 .
T (f indKmin(ϕ, B, ϕ)) = c2 for some constant c2 .
T (f indKmin(ϕ, ϕ, C)) = c3 for some constant c3 .
Let c > max(c1 , c2 , c3 ). Then T (f indKmin(A, ϕ, ϕ)) < c ∗ logn, T (f indKmin(ϕ, B, ϕ)) < c ∗ log3n and
T (f indKmin(ϕ, ϕ, C)) < c ∗ logn.

T (f indKmin(A, B, C, k)) = T (f indKmin(A′ , B ′ , C ′ , k ′ )) + O(1) where O(1) is the time required for compar-
ing indexes and selecting the max/min element.
T (f indKmin(A′ , B ′ , C ′ , k ′ )) < c ∗ log(3n − n/2) for some c > max(c1, c2, c3)(By Induction Hypothesis).
Therefore, T (f indKmin(A, B, C, k)) < c ∗ log(3n) − c ∗ log(6/5) + O(1).
Let O(1) = d such that d > c*log(6/5).
Hence, T (f indKmin(A, B, C, k)) = O(log(3n)).
We have O(logn) time complexity.

Space Complexity :
Since our algorithm takes O(logn) steps and we pass 3 sliced arrays of O(n) space we have O(nlogn) as our
space complexity. Note that our space can be easily reduced to O(n) by passing pointers or indexes
instead of copies of array but we maintain the former due to readability reasons.

5 Pseudocode
A, B, C are sorted lists and we use 0-indexing. Please see next page for code.

6 Proof of Correctness
A, B, C are the three sorted lists. Let len(A), len(B), len(C) be lengths of the three arrays.
a = ⌊len(A)/2⌋
b = ⌊len(B)/2⌋
c = ⌊len(C)/2⌋
We consider two cases - k <= a + b + c and k > a + b + c
Case 1 : k > a + b + c
Without loss of generality, let A[a] be minimum element out of A[a], B[b] and C[c]. In this case, k th element
can not be an element of A less than or equal to A[a] because if that were true then b + c + a >= k which
is a contradiction. Therefore, we can restrict our attention to A[a + 1: ], B and C. Also we now have to find
(k − a − 1)th minimum element.
Case 2 : k <= a + b + c
Without loss of generality, let C[c] be maximum element out of A[a], B[b] and C[c]. In this case, k th element
can not be an element of A greater than or equal to C[c] because if that were true then a + 1 + b + 1 + c < k
which is a contradiction. Therefore, we can restrict our attention to A, B and C[ : c].
(Notation : we include the value before colon but exclude the one after it in C[x : y])
Therefore, we can be sure that the subproblem f indKmin(A[a + 1 :], B, C, k − a − 1) will always have the
(k−a−1)th minimum number. Also the subproblem f indKmin(A, B, C[: c], k) will always have the k th minimum
number.
In case one array is completely rejected, We define the middle element(a , b or c) of the respective array in
such a way that that array is never considered for rejection. So we can be sure that number of elements in our
array are reducing in size per iteration and we are not entering an infinite loop.

2
Algorithm 1 FindKMin
1: function findKMinAfterProcessing(A, B, C, k)
k ← k − 1;
findKmin(A, B, C, k);
2: end function
3: function findMin(a , b , c)
If(a < b and a < c) return a;
Else if(b < c and b < a) return b;
Else return c;
4: end function
5: function findMax(a , b , c)
If(a > b and a > c) return a;
Else if(b > c and b > a) return b;
Else return c;
6: end function
7: function findKmin(A, B, C, k)
If (len(A) = 0 and len(B) = 0)
8: return C[k];
If ((len(B) = 0 and len(C) = 0)
9: return A[k];
If (len(C) = 0 and len(A) = 0)
10: return B[k];
a ← ⌊len(A)/2⌋;
b ← ⌊len(B)/2⌋;
c ← ⌊len(C)/2⌋;
If (a + b + c < k)
If(len(A) = 0) a ← ∞;
If(len(B) = 0) b ← ∞;
If(len(C) = 0) c ← ∞;
Switch (findMin(A[a], B[b], C[c]));
Case(A[a]):
return findKmin(A[a+1 : ], B, C, k - a - 1);
Case(B[b]):
return findKmin(A, B[b+1 :], C, k - b - 1);
Case(C[c]):
return findKmin(A, B, C[c+1 :], k - c - 1);
Else
If(len(A) = 0) a ← −∞;
If(len(B) = 0) b ← −∞;
If(len(C) = 0) c ← −∞;
Switch (findMax(A[a], B[b], C[c]));
Case(A[a]):
return findKmin(A[ : a], B, C, k);
Case(B[b]):
return findKmin(A, B[ : b], C, k);
Case(C[c]):
return findKmin(A, B, C[ : c], k);
11: end function

3
 Finally, since all the arrays are sorted, when two arrays get rejected completely, the k th minimum ele-
ment(recursively defined) is A[k] where A is the remaining array without loss of generality.

End of document