I that tends to be so because once your data structure are set in stone, the complexity of the implementation follows. You can always work to improve performance, but without redesigning your basic concepts you'll only go so far.
There are similarities in other areas than theoretic complexity models. I tried a phone a while ago. It waws promising but the UI was far from smooth. The person I spoke with insisted that it's a first version and performance will surely improve. But if your basic drawing primitives isn't smooth by design, your final version will never be. The comparison is far from perfect of course, but provides food for my thoughts.