Should you measure mesh complexity in triangles or vertices? I have seen people using either vertices or triangles as a quick heuristic to estimate mesh memory usage and mesh rendering time.

I always thought vertices were better, because the number of vertices processed in the vertex shader is known, whereas the number of fragments rendered varies depending on depth complexity, distance to the screen, area of the triangles....

However it seems triangles are used just as often as vertices, if you need one to do a naive estimation, which one is better?
Since you're talking about "vertex shaders" and "fragments", I assume that your question is to be interpreted in the context of real-time rendering using the graphics pipeline on a modern GPU through some modern graphics API. Even if we narrow down the question like that, I don't think a general answer can be given to what you're asking. It depends a lot on what kind of meshes/scenes/application you're dealing with. In general, it's not even clear what "number of vertices" or "number of triangles" should mean exactly. There isn't really the number of vertices and the number of triangles. If you're rendering a non-indexed triangle strip, then there's a direct relation between the number of vertices and the number of triangles. If you're rendering an indexed triangle list, then do we count the number of vertices that were referenced, the number of vertices that were shaded, or do we count the number of indices that were used to form triangles? If you're rendering patches with tessellation, then is the number of vertices the number of control points or is it the number of vertices produced by the tessellation? What if I have a geometry shader that eats a few points, and turns them into loads of overlapping triangles? What if my geometry shading streams the odd triangle to a stream output buffer but doesn't send anything to the rasterizer at all!? The point is, there's a great many different places in a graphics pipeline where something that one might call a "vertex" or a "triangle" could pop up…

In a typical triangle mesh that is supposed to represent the boundary surface of some physical object, there will be a direct relationship between the numbers of vertices and triangles. In such cases, either the number of vertices or the number of triangles is arguably as good a measure as the other when it comes to giving an estimate of mesh complexity. But then, what "complexity" are we talking about exactly? Complexity in terms of storage can probably be estimated from either number of vertices or triangles as explained above. Complexity in terms of rendering time is a whole different story. Depending on your application, it might be that neither the number of triangles nor the number of vertices is a good predictor for performance at all. It's actually trivial to write a program that makes even the latest and greatest graphics card sweat by rendering only a single triangle using no vertex buffer. Because your bottleneck is rasterization, fragment processing, or the framebuffer, for example. In such a case, you'd probably be more interested in the number of fragments produced, or the depth complexity…