What is the complexity of the Block Korkine-Zolotarev algorithm?

It's not a complexity that lends itself readily to useful estimates and parameters for current levels of cryptographic interest. The complexity is usually stated in terms of a number of calls to a subroutine (often termed an oracle) that solves a short-ish vector problem in a space of dimension $\beta$, the block size. (Specifically a short-ish vector problem in the space defined by components of $\beta$ consecutive basis vectors that are orthogonal to all preceding basis vectors). The larger the block size, the more complex the subroutine, but the "better" the resulting basis.

As the linked Li-Nguyen paper equation (1) states, the BKZ alogrithm for a lattice of dimension $n$ should take $O(n^2(\log n)/\beta^2)$ "tours" to complete, where each tour has $n$ calls to the aforementioned subroutine as the main contribution to the work. Thus the work can be summarised as $O(n^3(\log n)/\beta^2)$ calls to the subroutine.

This can be helpful when $\beta$ is fixed and the dimension $n$ varies as it can provide proportional work estimates for higher dimensions relative to lower dimensions. For variable $\beta$ we need to consider the cost of the SVP subroutine and here is where things can be unhelpful. For $\beta=1$, the subroutine is trivial and BKZ is the same as LLL. For $\beta=2,3,4,5$ there are very efficient SVP algorithms with similarly trivial overheads. As $\beta$ grows large, the best asymptotic algorithms are sieve algorithms where the cost is $(3/2)^{\beta/2+o(\beta)}$, but with a high memory usage. In examples of BKZ in practice, parameters are not always close to the regime where the sieving approach is best. Instead for the size of $\beta$ for many problems of interest a SVP approach from (trimmed) Schnorr-Euchner enumeration is usually best. Trimmed Schnorr-Euchner approaches have complexities of the form $\exp(c\beta\log\beta)$ for various parameterisations and approaches.

Anyway, one can argue that by our current knowledge of the complexity of BKZ for large dimension and large block size is given by $$n^3(\log n)\left(\frac 32\right)^{\beta/2+o(\beta)}$$ but any numerical usage of this estimate is unlikely to be helpful for security estimates. A better approach might be to fix a block size, get reliable estimates for a short-ish vector subroutine for this block size and then scale by $n$ times the asymptotic estimate for the number of tours. The lattice estimator software may be able to help with much of this.