> I think the basics of data-structure choice should be easily within the realms of an LLM's current capabilities.

Surprisingly, it isn't. I catch the output of LLMs breaking these rules all the time. Just as it is pretty common in general programmer code.

The greatest sin I often find isn't necessarily Big-Oh related but rather multiple traversal problems. Much like regular programmers, LLMs love to do multiple passes over the same list to extract data. For example

    let cats = pets.filter((p)->p.isCat());
    let dogs = pets.filter((p)->p.isDog());

A lot of programmers are oblivious to that sort of performance issue. It comes up a lot.