From aaf96ede0b3936c1e6905a315688e8c0895e02e0 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 20 Sep 2020 18:27:57 -0600 Subject: docs: complete question 3 --- src/03/03/README.md | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'src/03') diff --git a/src/03/03/README.md b/src/03/03/README.md index f69b22e..a8bd4af 100644 --- a/src/03/03/README.md +++ b/src/03/03/README.md @@ -2,4 +2,21 @@ Suppose you are given two sequences S1 and S2 of `n` elements, possibly containing duplicates, on which a total order relation is defined. 1. Describe an efficient algorithm for determining if S1 and S2 contain the same set of elements. + +Since S1 and S2 has a total order relation defined this means +that the data is sorted in both sequences. + +To tell if the S1 and S2 contain the same set of elements we can use two pointers +to walk through each item in each sequence one step at a time to compare the values +at each index to ensure they are a match. As soon as we detect a mismatch +we know that the sequences do not contain the same set of elements. If we can +iterate to the end of both sequences at the same time then we have a match. + 1. Analyze the running time of this method. + +The time complexity is dependent on the size of `n` elements and is +therefore a linear time algorithm `O(n)`. + +The space complexity is constant, `O(1)`, because only two pointers +are needed to walk through both sequences. The amount of space required +to perform this algorithm does not change as the input size of `n` changes. -- cgit v1.2.3