Alternatives to "computationally expensive"?

The correct answer will depend on your audience. For a highly technical audience such as engineers and programmers, you could keep the original sentence or use one of the more precise terms suggested by Midhat. Everyone in that audience will immediately understand your message because they are already familiar with the underlying concepts. To them, the important information is the how and the why, and your sentence delivers.

For a less technical audience that is still somewhat familiar with the technology, I would choose a term that has more specific meaning for the members of that audience:

• We can improve [algorithm] by making [such and such] more efficient
• [such and such] requires more (time/memory) than any other part of [algorithm]
• [algorithm] does not meet our needs because it spends so much time on [such and such]

For a non-technical audience like high-level management, the technical details should be an afterthought. If you are worried that the term "computationally expensive" is overkill for your audience, you should probably remove the other technical details as well. This does not imply that your audience is too stupid to understand what you are saying, just that they are more interested in other things:

• We can improve [business application] by spending more money on [resource] (for [algorithm])

resource intensive, CPU intensive, Memory intensive

• Puts a heavy workload on the CPU.

The wording is less technical so your general audience will understand, and to a technical audience they will understand it just as well, with not much room for misunderstanding.

I guess you could say it takes up a lot of CPU time, memory, or both. Which is also more precise.