Which is faster for large n: O(n) or O(n^2), and why?

O(n) is far faster at scale. If you make the input 1000x bigger, an O(n) algorithm does about 1000x the work, while an O(n^2) algorithm does about 1,000,000x the work.

So a nested-loop O(n^2) solution that looks fine on 100 items can be unusable on a million, and switching to an O(n) approach (often by using the right data structure, like a HashSet) beats any amount of micro-optimizing the slow one.