Compressible Navier-Stokes vs Incompressible, which is 'Easier' or usually has shorter computation times for finding numerical solutions? This is a broad question which might not have a clear answer. I am aware that the incompressible NS equations can be used to approximate the compressible when the Mach number is low, and that this approximation is validated by results in functional analysis.
However, I am currently wondering what the 'use' is for this approximation. I remember during my bachelor's degree in physics lessons that we were taught that this approximation was useful as the incompressible version was 'easier' for computing (by hand) exact solutions in specific cases like pipe flow. This just seemed intuitive to me at the time, as there were of course fewer terms.
Does this hold true when computing numerical solutions though? Is the incompressible version easier in most or even any cases?
I ask as I am aware that the incompressible version can have its own set of problems (for example one can't use the barotropic assumption that the pressure is just the density to the power of some constant in the incompressible case). So perhaps no broad comparisons between the two make sense?
 A: The incompressible case is easier; I don't think it is stated in any source directly (because it is just known), but it is well known and I can tell you why. The incompressible case simplifies the physics and the space of degrees of freedom by assuming that $\nabla\cdot u = 0$. Physically, this eliminates lots of behaviors that are numerically difficult, most importantly shock waves. If you look at solvers for the compressible case (e.g. Riemann solver), a lot of work is spent managing these phenomena and accurately representing them, which is just not an issue here. Shocks are a particular problem because they introduce discontinuities and numerical conditioning issues; people have been struggling with this since the dawn of numerics, which is probably why finding a source that says "and we all know this case is harder" is hard.
Additionally, in many numerical schemes,$\nabla\cdot u = 0$ directly enables fast and efficient algorithms. The basics are that we represent the linearization of incompressible Navier-Stokes system as a block matrix where there is a velocity-velocity block $A$, velocity-pressure block $B$,  pressure-velocity block $B^{T}$, and pressure-pressure block $C$ (but this is $C=0$ since pressure interacts through velocity):
$
  X = \left[\begin{array}{ c | c }
    A & B \\
    \hline
    B^{T} & C
  \end{array}\right]
$
The consequence of $\nabla\cdot u = 0$ is that $B^{T}$ is easier to deal with. Since $C=0$, this means you have a system:
$
  X = \left[\begin{array}{ c | c }
    A & B \\
    \hline
    B^{T} & 0
  \end{array}\right]
$
which almost looks like you could solve $B^{T}$ first and then solve the rest (Look up Schur complements). This is not too far from the truth as there are many schemes that in this case let you solve just with velocity and then recover pressure. This is only possible with incompressibility. More generally, we just have a good numerical idea how to deal with $B^{T}$ in the context of the this system.
A: There are several points that Wraith1995 made that experts in incompressible flows would take exception with.
While it is true that the incompressible assumption circumvents challenging aspects such as shocks and reduces the number of unknowns, it introduces a host of other issues. In my opinion, these can often be just as difficult (or more so) to overcome as the unique issues encountered in compressible flows. A simple analog for incompressible flows is to think back to statically indeterminate beams from a statics course. Both are overconstrained, which prevent any straightforward computation of the internal forces.
The main problem is exactly opposite of what Wraith said about the matrix structure. The zero block in the pressure-pressure location certainly does not help in any way; it is precisely the opposite. The zero block indicates a saddle-point problem, which are known to be extremely pesky to deal with. In this sense, pressure is acting as a Lagrange multiplier, which adjusts instantaneously to enforce the continuity equation. In effect, the pressure field, which evolved hyperbolically in the compressible equations, is now elliptic, and there is no good way to march pressure in time. No matter how you choose to deal with this, you effectively have an infinitely (or close to it) stiff system of equations, which is a nightmare to solve efficiently. There are many other practical challenges that result from this, such as the Ladyzhenskaya–Babuška–Brezzi condition, which is the underlying mathematical reason for many people using staggered grids for incompressible CFD.
On the contrary, the compressible equations have a fundamentally different structure. There is a time derivative for all unknowns, which can be said to constitute a Cauchy problem (incompressible Navier-Stokes is not a Cauchy problem). Consequently, the very well-studied field of ODEs can be more or less directly applied to integrate the semi-discrete equations in time. However, discretizing the incompressible equations in space does not result in a system of ODEs; rather, a differential-algebraic equation (DAE) system is obtained. Another way of saying this is that the semi-discrete compressible equations form a system of ODEs, while the semi-discrete incompressible equations form a system of ODEs that are subject to algebraic constraints.
Much less is known about DAEs, and it is usually counterproductive to apply ODE theory to them.
An excellent text on this issue is "Incompressible flow and the Finite Element Method" by Gresho and Sani (1998). I'll refer you to P.361, where they make the following quote:

The implications of the "simplification" of the mass conservation equation are actually quite profound---both theoretically and numerically; indeed, the simplification comes at a higher cost than many might imagine before actually "diving in." In many ways, the incompressible NS equations are more difficult to solve than their compressible progenitors---especially for "neophytes" who believe otherwise.

Anyway, I think the proper answer to your question of which is harder is that it depends. They each have their own unique challenges, but I think it is wrong to say one is always more difficult than the other. Transonic flows around a complex vehicle might be very difficult to solve compared to a relatively slow incompressible pipe flow. However, a fully-enclosed incompressible flow can pose more difficult challenges than a supersonic flow past a simple geometry.
