where can i find the O complexity of java methods?
Sometimes it is specified in the documentation, but many times you just have to reason about it on your own.
I actually need to end up with a list (to fit method signature in interface definition), so I would have to convert the linkedHashset back to a list, but this would still be O(n) (right?)
Yes that's still O(n) (O(2n) == O(n)). Further you could do it in a one-liner