Time complexity of removing duplicates in lists
The running time is expected $O(n)$ for both problems.  Simply scan over the input list, and as you examine each item, add it to the hashtable; if it wasn't already present, output it.  The running time is $(n)$ because, with a suitable hash function, the expected time it takes to insert or look up an item in a hash table is $O(1)$.

The worst-case running time with this approach is $O(n^2)$, but you can make the probability of this happening exponentially small with a suitably chosen hash function.

Alternatively, if you care a lot about worst-case running time, you can replace the hashtable with a self-balancing binary tree and achieve $O(n \log n)$ worst-case running time for both problems.