Q:

Speed of ConvexHullMesh

Pick $N$ random points on the surface of the sphere, then use ConvexHullMesh[] to  compute their convex hull. Empirically, this takes time quadratic time in $N,$ whereas the state of the art as of 1996 is $N \log  N.$ Is Mathematica  doing something extra, or is its algorithm just 18 years out of date?
In the interest of "politeness".
randpt[n_]:= Module[{prept = RandomVariate[NormalDistribution[], 3]}, prept/Norm[prept]]
experiment[n_]:= ConvexHullMesh[Table[randpt[3], {n}]//AbsoluteTiming

EDIT
Here is the experimental data (the first element in each pair is the number of points, the second the AbsoluteTiming [this on a very fast Windows PC])
{{10000, 6.133357}, 
 {20000, 17.791034},
 {30000, 50.460951},
 {40000, 106.783207},
 {50000, 182.384594}}

This looks awfully quadratic to me. I point out that experiments for small $n$ are meaningless, since there is linear overhead, which has a none-too-small constant, so swamps the quadratic growth. $50000$ points is not that many (and certainly would be a modest number for any FEM mesh), so this is clearly a major performance bug.
ANOTHER EDIT for comparison purposes, I also installed qhull on the very same machine, and ran qconvex on 50000 cospherical random points. The running time was, umm, well, it started spewing output at me the moment I hit return, so I am seeing a roughly three order of magnitude speedup.

A:

It appears to be just as it should be here (v10.0.0 under Windows):
randpt[n_] := With[{prept = RandomVariate[NormalDistribution[], 3]}, prept/Norm[prept]]

Needs["GeneralUtilities`"]

BenchmarkPlot[{ConvexHullMesh}, Table[randpt[3], {#}] &,
 "IncludeFits" -> True,
 TimeConstraint -> 30
]

Following your update I tried a plot with larger n values as indicated.  The result:

Indeed it seems there is an issue with scale.  I am not familiar with the algorithm so I don't know if this should be considered a designed trade-off or a bug.

A:

The best you may hope for is the speed of TetGen as that is the underlying engine of the convex hull computation. The increase of timing you see comes from the fact that a MeshRegion needs to check the consistency. You can switch that consistency check of for ToBoundaryMesh (and there are a few other checks you can switch off, please see the documentation for ElementMesh here)
Needs["NDSolve`FEM`"]
Needs["TetGenLink`"]
randpt[n_] := 
 With[{prept = RandomVariate[NormalDistribution[], 3]}, 
  prept/Norm[prept]]

Needs["GeneralUtilities`"]

BenchmarkPlot[{ToBoundaryMesh[#, "CheckIntersections" -> False] &, 
  TetGenConvexHull}, Table[randpt[3], {#}] &, 100, 
 "IncludeFits" -> True, TimeConstraint -> 60]

TetGen is used for the convex hull computation. Unfortunately, TetGen will compute a Delaunay tetrahedralization and the hull will be extracted from that. That is why you see a speed discrepancy compared with 'qconvex'. This may change in a future version.

A:

Quadratic?
randpt[n_] := Module[{prept = RandomVariate[NormalDistribution[], 3]}, 
  prept/Norm[prept]];
experiment[n_] := First[AbsoluteTiming[ConvexHullMesh[Table[randpt[3], {n}]];]];
ListPlot[experiment /@ Range[500]]

