Perhaps a way to refine this understanding is to consider a different medium more typically believed to be artistic: film.
A director will construct the artistic vision (akin to the requirements/concept) and then work with film music composer to add music (analogous to development). Is the composer and artist practicing art? I would suggest that the word "craftsman" is better suited to the work the film composer does (assuming that they aren't also directing). That doesn't mean that a film composer cannot also be an artist in his/her own right, but in this context their input is arbitrarily limited by the artistic vision of the director... even if the director's vision allows for significant discretion by the composer.
Most development work, as you point out, has this separation of creative impulse from the implementing crafts. I do think there is "art" involved in programming, but only when the creative impulse is joined with the craft of development in a single mind.
I would argue that in those cases, programming is not an art because the arriving at the solution is very mechanical and there is literally zero room for creativity. Thus imo this answer isn't broad enough to fully define "Art"
Slathering paint onto a surface isn't always art.
Big Oh has to do with large N.
"If a program manipulates a large amount of data, it does so in a small number of ways." --- Epigram 5, Alan Perlis
"For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run." -- Alan Perlis
"Don't do things that scale" -- P. Graham
>Concept + skillful rendering = art
This statement does not fully cover the definition of art.
Change the x that the big O is about, for example by using vector instructions.
Implement a theoretically less efficient algorithm that is faster (examples: switch to a O(n^2) sort for small data set, or to a linear search for smallish arrays)
Unfortunately, that is frequently also the recipe for a big ball of mud [1]. I guess the beauty is in the eye of the beholder...