The complexity of direct solver for SPD problems depends essentially of the properties of the underlying graph. If your matrix comes from the discretization of an elliptic equation then it depends essentially on the mesh/ structure which supports the discretization. This is due to the fact that direct methods are based on elimination of unknowns which can generate fill-in (ie denser subgraphs) and therefore more work in the forecoming eliminations.
For instance if the graph of your matrix is a tree you can eliminate unknowns one by one and the complexity of a direct solver is $O(n)$ where is the number of nodes in the graph.
However if the graph is a planar graph (a graph that you can draw on a 2d plane), a well known result by Tarjan and Rose (1979) shows that the complexity is $O(n^{3/2})$.
Thanks to their structures, those graphs provide fast elimination and are good candidate for direct methods.
However, at the other side of the spectrum, there are some graphs for which the complexity is maximal like complete graph for which we get $O(n^3$), their corresponding matrices are dense matrices.