Asked By : Panarit
Answered By : Gilles
while list1 is not empty: if list2 is empty or head(list1) < head(list2): return false else if head(list1) = head(list2): let x = head(list1) while list1 is not empty and head(list1) == x: advance(list1) while list2 is not empty and head(list2) == x: advance(list2) else: (head(list1) > head(list2)) advance(list2) return true
Exercise: prove that this algorithm returns true when all the elements of list1 occur in list2 and false otherwise. Let $n_1 = mathrm{length}(mathtt{list1})$, $n_2 = mathrm{length}(mathtt{list2})$ and $n = max(n_1, n_2)$. The algorithm above removes at least one element of list2 at each iteration, and in the worst case it removes all the elements of both list. Therefore it executes at most $n_2$ iterations of the loop and performs at most $n_1 + n_2$ removals of the head of the list: its complexity is $O(n)$. Now suppose that the lists are not sorted. An obvious solution is to sort them, then apply the known algorithm. Since sorting is $O(n log n)$, this algorithm is $O(n log n)$. Exercise: make sure you understand why my statements about complexity are true. Exercise (difficult!): can you do better than $O(n log n)$ in the general case?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18346