# Sequence lenght analysis of the Solovay-Kitaev Algorithm

In the paper by Dawson and Nielsen where they develop an algorithm for the Solovay-Kitaev Theorem, they analyze the lenght of the output noting how, for an approximation of degree $$n$$, the lenght of the output sequence is $$5l_{(n-1)}$$ where $$l_{(n-1)}$$ is the lenght of the sequence for the approximation of degree $$n-1$$. They conclude that the algorithm produces a sequence asymptotically of lenght $$O(5^n)$$.
We can then work on the recurrence for the approximation error $$\epsilon_n$$, and by isolating $$n$$ we arrive at this formula: $$n = \left \lceil {\frac{\ln\left(\frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)}\right)}{\ln\left(\frac{3}{2}\right)}}\right \rceil$$
Then they affirm how substituting the right hand side of this formula into $$O(5^n)$$ allows us to rewrite it in terms of $$\epsilon$$ to get the result stated in the theorem of page 4 of the paper: $$O\left(\ln\left(\frac{1}{\epsilon}\right)^{3.97}\right)$$, but I don't get wich passages we need to perform to arrive at such conclusion. Can anyone help me?
Thank you.

They use the rule of conversion of logarithms: $$\log_b x = \frac{\log_c x}{\log_c b}.$$
For clarity define the following quantity: $$A:= \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)}.$$ Now we can write $$n = \left \lceil {\frac{\ln \left( \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)} \right)}{\ln(3/2)}}\right \rceil = \left \lceil {\frac{\ln(A)}{\ln(3/2)}}\right \rceil.$$
We use the log conversion rule to rewrite $$\ln(A)$$: $$\ln(A) = \frac{\log_5 A}{\log_5 e}.$$ So we get $$n = \left \lceil {\frac{\frac{\log_5 A}{\log_5 e}}{\ln(3/2)}}\right \rceil.$$ Now, substitute the above equation into $$O(5^n)$$ and ignore the ceiling operation with the Big $$O$$: $$5^n = 5^{\frac{\frac{\log_5 A}{\log_5 e}}{\ln(3/2)}} = \left ( 5^{\log_5 A} \right)^{\frac{\frac{1}{\log_5 e}}{\ln(3/2)}} = (A)^{\frac{\frac{1}{\log_5 e}}{\ln(3/2)}}.$$ Next, we use the log conversion again to rewrite $$\log_5 e$$ as follows: $$\log_5 e = \frac{\ln e}{\ln 5} = \frac{1}{\ln 5}.$$ Hence, we can write $$5^n = (A)^{\frac{\ln 5}{\ln(3/2)}}.$$ So, we have $$5^n = (A)^{\frac{\ln 5}{\ln(3/2)}} = \left( \frac{\ln(1/\epsilon \cdot c_{appr}^2)}{\ln(1/\epsilon_0 \cdot c_{appr}^2)} \right)^{\frac{\ln 5}{\ln(3/2)}}.$$
Note that $$\ln(1/\epsilon_0 \cdot c_{appr}^2)$$ is constant in $$\epsilon$$, so it will disappear when we push it through Big $$O$$. Also, we can absorb the constant $$c^2_{appr}$$ into $$\epsilon$$. Therefore, we get the final result: $$l_{\epsilon} = O\left( \ln(1/\epsilon ) ^{\frac{\ln 5}{\ln(3/2)}} \right).$$ We also have $$\frac{\ln 5}{\ln(3/2)} \approx 3.97$$. So we get the result in the theorem: $$l_{\epsilon} = O\left( \ln(1/\epsilon ) ^{3.97} \right).$$
We can do the same thing for $$O(3^n)$$ to get : $$t_{\epsilon} = O\left( \ln(1/\epsilon ) ^{\frac{\ln 3}{\ln(3/2)}} \right).$$ The above can also be written as presented in the theorem: $$t_{\epsilon}= O\left( \ln(1/\epsilon ) ^{2.71} \right).$$