The Bowyer-Watson algorithm for Delaunay triangulation is known to run in O(n^2) according to the authors, where n is the number of data points in R^d.
In addition, the algorithm (for example, as is written in Bowyer's paper, at stage 5 of the algorithm), runs over all the simplexes, (also runs over simplexes that will be later deleted).
How does it settle with the fact that there are O(n^{d/2}) simplexes in Delaunay triangulation?
One should expect from the algorithm to run in Omega(n^{d/2}), (and maybe even in a worse time complexity - since it runs over "extra simplexes").
Thanks!