If i had to compare the two lists to find the common items, which method will be more efficient performance wise and why?
1) Iterating and comparing the two lists using two for loops
2) Use List.Contain() method?

Could be either. List.Contains uses a for loop internally, so you won't avoid the for loop simply by using List.Contains.

That being said, there's a couple of additional checks within Contains that you can avoid by making your own for loop (for example, Contains checks for null... you can eliminate this step by implementing the comparison yourself if you know that none of the items will actually be null).

I'd encourage you to get a copy of Reflector, and check out the implementation of List.Contains yourself to see how it's implemented.

Your next step is to create a test to see which is faster. Implement the comparison two separate ways, and run each implementation several times, timing each set of iterations. This is the best way to check your performance... to actually see how long it takes yourself.

---

Coding Light - Illuminated Ideas and Algorithms in Software
Coding Light Wiki �LinkedIn �ForumsBrowser

By the way you can improve the performance a lot by either sorting the lists or using a Dictionary / HashTable.

Either way has O(n^2) complexity, technically O(n * m). A list that is twice as long is going to take 4 times as much time. You can get ahead by sorting the shorted list first, then using List.BinarySearch() to search it. Sorting is O(n * log(n)), comparing is O(m * log(n)). If the list items are unique consider a HashSet, O(n) to create it, O(m) to compare. It requires storage though.

---

Hans Passant.

Hello

Thank you everyone for your excellent analysis of algorithm based on the big O.

Ibtesam, if you want a simple coding version, please refer to this sample code:

using System.Linq;

int[] elementSet1 = { 5, 1, 6, 3, 8 };
int[] elementSet2 = { 3, 7, 8, 6, 5 };

foreach (int element in elementSet1.Intersect(elementSet2))
{ Console.WriteLine(element); }

Inside the Intersect extension method, it does something like this:

public static IEnumerable<T> Intersect<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
Dictionary<T, object> dict = new Dictionary<T, object>();
foreach (T element in first) dict[element] = null;
foreach (T element in second)
{
if (dict.ContainsKey(element)) dict[element] = dict;
}
foreach (KeyValuePair<T, object> pair in dict)
{ if (pair.Value != null) yield return pair.Key; }
}

Regards,
Jialiang Ge

---

Please remember to mark the replies as answers if they help and unmark them if they provide no help.
Welcome to the All-In-One Code Framework! If you have any feedback, please tell us.

That's an O(n^2) algorithm with O(n) storage requirement, hard to do worse.

---

Hans Passant.

Seems to be O(n+m) to me.