Sub Algorithm I is $O(n^4\log n)$.

The time of repeating Step 6 in Sub Algorithm II is $t$ $=$ $O(Br(C)/\operatorname{ham}(C))$, and for each time the running time is $O(n^2)$, hence, the complexity of Sub Algorithm II is $O(n^2*t)=O(n^2Br(C)/\operatorname{ham}(C))$, where $\varepsilon^{-2}\log\delta^{-1}$ has been put into the term $O(\cdot)$ for simplicity. As we know, the Hamiltonian Recovery Algorithm takes $O(n^2)$ time. After removing Hamiltonian Recovery procedure, the total running time of Sub Algorithm II is still $O(n^2*t)$, thus if approximating $\operatorname{ham}(A_G)$ is only the purpose, outputting the Hamiltonian cycle is the byproduct of Sub Algorithm II.

If the digraph $G$ is $\alpha n$ dense, $\alpha
>.5$, an important result given by Huber[@HL08] is $$Br(C)/\operatorname{per}(C)=O(n^{-.5+.5/(2\alpha-1)}).$$ Note that\
$$\begin{split}
 \frac{\operatorname{per}(C)}{\operatorname{ham}(C)}&=
  \frac{\prod\limits_{i=1}^n(X(i,i)Y(i,i)Z(i,i))\operatorname{per}(A^{\varepsilon}_G)}
 {\prod\limits_{i=1}^n(X(i,i)Y(i,i)Z(i,i))\operatorname{ham}(A^{\varepsilon}_G)}
 =\frac{\operatorname{per}(A^{\varepsilon}_G)}{\operatorname{ham}(A^{\varepsilon}_G)}.
\end{split}$$ If the digraph $G$ is at least $.5n$ dense, then changing any zeros in $A_G$ to $\varepsilon n^{-3}$ increases $\operatorname{per}(A_G)$ by at most a factor of $1+\varepsilon$ [@JS89]. Then $$\begin{split}
  \frac{\operatorname{per}(C)}{\operatorname{ham}(C)}
  =\frac{\operatorname{per}(A^{\varepsilon}_G)}{\operatorname{ham}(A^{\varepsilon}_G)}
  \leq\frac{(1+\varepsilon/3)\operatorname{per}(A_G)}{\operatorname{ham}(A_G)}
 =O(\frac{\operatorname{per}(A_G)}{\operatorname{ham}(A_G)}).
\end{split}$$ Hence, the total running time of our algorithm is $$\begin{split}
O(n^4\log n+ n^2\frac{Br(C)}{\operatorname{ham}(C)})&= O(n^4\log n+
n^2\frac{Br(C)}{\operatorname{per}(C)}\frac{\operatorname{per}(C)}{\operatorname{ham}(C)})\\
&=O(n^4\log n+
n^{1.5+.5/(2\alpha-1)}\frac{\operatorname{per}(A_G)}{\operatorname{ham}(A_G)}).
\end{split}$$ Now we present combinatorial argument on the bound of $\frac{\operatorname{per}(A_G)}{\operatorname{ham}(A_G)}$(Recall $A_G$ is a 0-1 matrix and all the edge weight of $G$ equals one). The 