(May-20-2020, 12:12 PM)hussainmujtaba Wrote: A list can have the same element multiple times, when converting it to a set, it ll only contain element once. Thus the search space has decreased and it 'll be faster.
This really isn't correct reasoning. Consider a list of length n containing unique items. The performance of the search isn't going to be the same as for a set. With a list, you either have to do a search through the entire thing to find the item you want (which at worst takes time proportional to n, hence why this is called a linear search) or if the list is sorted, perform a binary search (which at worst takes time proportional to log_2 n). Sets are based on hash tables, meaning that items are stored in buckets based on their hash value (a number representing them). Searching for an item means computing its hash (which should be fast!) and then using that as an index into this table, which is an array-like thing, meaning that looking up something by index (and consequently search) is done in constant time (i.e. independent of n). I suspect the constants of proportionality here mean that the difference is going to be noticeable only for sufficiently large n.