Once I made a Ruby program noticably slow by using "array += items" instead of "array.push *items" in a loop, making it O(n^2) instead of O(n). Once we noted that doubling the input size quadrupled the runtime, I found the bug. (I was a Ruby newbie and didn't know that Ruby's "array += items" is just syntactic sugar for "array = array + items".)

I've used slow web pages that show a lot of items or data. One way to make them slow is O(n^2) DOM manipulation (e.g., inside a loop over items in a page, O(n)-searching the page for something).

Knowing complexity theory isn't the only way to find performance problems, and sometimes isn't even relevant, but it sure is helpful.