Mazdak Farrokhzad edited c) Imposing a restriction.tex  about 10 years ago

Commit id: 2b9102023ba0c1a7ed9bc2af30a6870726c5e337

deletions | additions      

       

\end{algorithmic}  \end{algorithm}  The number of calls, which will be our elementary operation and thus the time complexity, can be visualized and divided into two "geometric" shapes, one triangle shaped phase where with the complexity being the "area" given by the value: $A_1$. Under this phase the number of calls to the next i:th level keeps growing linearly by $2$ for each level until it reaches $\phi(x,i)$. $\delta(x,i)$.  When it does, it will continue from $\phi(x, i) + 1$ to $i$ but for each level, the amount of calls per level won't grow anymore, but instead stay constant at the highest value before with one added to it. This phase is shaped like a rectangle. If the step size $c$ is larger, this phase will start sooner. In mathematical terms: \begin{subequations}  \begin{align*}  \phi(x,i) \delta(x,i)  &= \ceil{\frac{x}{a}}\\ A_1 &= \sum_{k=1}^{\phi(x,i)}\left[ \sum_{k=1}^{\delta(x,i)}\left[  2(k - 1) \right]\\ A_2 &= \left[ 2\phi(x,i) 2\delta(x,i)  - 1 \right]\left[ i-g(x) i-\delta(x)  \right] \end{align*}  \end{subequations}